Warum verwendet die Log-Rank-Vermutung Rang über den Real?

10

In der Kommunikationskomplexität besagt die Log-Rank-Vermutung, dass

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

Wobei cc(M) die Kommunikationskomplexität von M(x,y) und rk(M) der Rang von M (als Matrix) über den Realwerten ist.

Wenn Sie jedoch nur die Rangmethode verwenden, um die Grenze zu senken, cc(M)können Sie rk über jedem Feld verwenden, das zweckmäßig ist. Warum beschränkt sich die Log-Rank-Vermutung darauf, über die Reals zu rken? Wird die Vermutung für rk über Felder ungleich Null aufgelöst? Wenn nicht, ist es von Interesse oder hat etwas Besonderes an Rrk über R ?

Artem Kaznatcheev
quelle
2
Übrigens, ich glaube, Sie sollten M auf binär beschränken, sonst können Sie triviale Gegenbeispiele erfinden.
Sasho Nikolov
@SashoNikolov Was meinst du mit trivialen counterexamples wenn M nicht ist 0/1 (I Sie reellen Zahlen bedeuten über glauben)?
T ....
Zum Beispiel das Problem "rate meine Nummer", dh Alice hat eine Nummer in und Bob muss sie ausgeben. Es ist leicht zu erkennen, dass die Kommunikationskomplexität log N ist, aber der Rang der Matrix ist 1 . {1,,N}logN1
Sasho Nikolov
@SashoNikolov Kannst du meine Nummer genau erraten? Ich kann die charakteristische Matrix nicht visualisieren. Alice hat und Bob hat y . Was ist dann die Funktion f ( x , y ), aus der M von Rang 1 definiert ist? xyf(x,y)M1
T ....
1
Die Funktion ist , wo x und y sind n -Bit - Vektoren. Wenn die Definition der Kommunikationskomplexität erfordert, dass der Wert von f vollständig durch das Protokolltranskript bestimmt wird (dies ist die Definition in Kushilevitz-Nisan), dann ist die Komplexität eindeutig n . f(x,y)=xxynfn
Sasho Nikolov

Antworten:

14

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

Sasho Nikolov
quelle