Mengapa dugaan log-rank menggunakan peringkat di atas real?

10

Dalam kompleksitas komunikasi, dugaan log-rank menyatakan hal itu

cc(M)=(logrk(M))O(1)

Di mana adalah kompleksitas komunikasi M ( x , y ) dan r k ( M ) adalah pangkat M (sebagai matriks) atas real.cc(M)M(x,y)rk(M)M

Namun, bila Anda hanya menggunakan rank-metode untuk menurunkan terikat Anda dapat menggunakan r k atas setiap bidang yang nyaman. Mengapa dugaan log-rank terbatas pada rk atas real? Apakah dugaan diselesaikan untuk r k atas bidang karakteristik non-nol? Jika tidak, itu menarik atau ada sesuatu yang khusus tentang r k lebih R ?cc(M)rkrkrkR

Artem Kaznatcheev
sumber
2
BTW Saya percaya Anda harus membatasi menjadi biner, jika tidak, Anda dapat membuat contoh tandingan sepele. M
Sasho Nikolov
@SashoNikolov Apa yang Anda maksud dengan tandingan sepele jika tidak 0 / 1 (saya percaya Anda berarti lebih real)? M0/1
T ....
{1,,N}logN1
xyf(x,y)M1
1
f(x,y)=xxynfn

Jawaban:

14

F2M(x,y)=x,ymod2x,y{0,1}nΩ(n)MF2n

Sasho Nikolov
sumber