¿Por qué la conjetura del rango logarítmico usa el rango sobre los reales?

10

En la complejidad de la comunicación, la conjetura de log-rank establece que

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

Donde cc(M) es la complejidad de comunicación de M(x,y) y rk(M) es el rango de M (como una matriz) sobre los reales.

Sin embargo, cuando solo está usando el método de rango para reducir el límite cc(M) , puede usar rk sobre cualquier campo que sea conveniente. ¿Por qué la conjetura de log-rank se restringe a rk sobre los reales? ¿Se resuelve la conjetura para rk sobre campos de características distintas de cero? Si no, ¿es de interés o hay algo especial sobre rk sobre R ?

Artem Kaznatcheev
fuente
2
Por cierto, creo que debes restringir M para que sea binario, de lo contrario puedes inventar contraejemplos triviales.
Sasho Nikolov
@SashoNikolov ¿Qué quiere decir por contraejemplos triviales si M no es 0/1 (creo que decir sobre reales)?
T ....
{1,,N}logN1
xyf(x,y)M1
1
f(x,y)=xxynfn

Respuestas:

14

F2x , y { 0 , 1 } n Ω ( n ) M F 2 nM(x,y)=x,ymod2x,y{0,1}nΩ(n)MF2n

Sasho Nikolov
fuente