Pourquoi la conjecture log-rank utilise-t-elle le rang sur les réels?

10

Dans la complexité de la communication, la conjecture log-rank déclare que

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

est la complexité de communication de M ( x , y ) et r k ( M ) est le rang de M (sous forme de matrice) sur les réels.cc(M)M(x,y)rk(M)M

Cependant, lorsque vous utilisez simplement la méthode de classement pour réduire la limite vous pouvez utiliser r k sur n'importe quel champ qui vous convient. Pourquoi la conjecture log-rank se limite-t-elle à rk sur les réels? La conjecture est-elle résolue pour r k sur des champs de caractéristique non nulle? Sinon, est-ce intéressant ou y a-t-il quelque chose de spécial à propos de r k sur R ?cc(M)rkrkrkR

Artem Kaznatcheev
la source
2
BTW Je pense que vous devriez limiter à être binaire, sinon vous pouvez créer des contre-exemples triviaux. M
Sasho Nikolov
@SashoNikolov Que voulez - vous dire par contre - triviale si est pas 0 / 1 (je crois que vous dire sur reals)? M0/1
T ....
{1,,N}logN1
xyf(x,y)M1
1
f(x,y)=xxynfn

Réponses:

14

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

Sasho Nikolov
la source