Dlaczego przypuszczenie log-rank używa rangi nad rzeczywistością?

W złożoności komunikacyjnej domniemanie log-rank stwierdza, że

c c (M) = (\log r k (M))^{O (1)}

$cc(M) = (\log rk(M))^{O(1)}$

Gdzie jest złożoność komunikacji , a jest rangę (jako matrycy) w liczb rzeczywistych. $cc(M)$ $M(x,y)$ $rk(M)$ $M$

Jednak, gdy jesteś po prostu za pomocą szeregowych metodę dolna granica można użyć na każdym polu, które jest wygodne. Dlaczego domniemanie log-rank ogranicza się do rk ponad rzeczywistością? Jest przypuszczenie rozwiązany za nad polami charakterystycznych niezerowej? Jeśli nie, to czy jest interesujące, czy jest coś specjalnego w nad ? $cc(M)$ $rk$ $rk$ $rk$ $\mathbb{R}$

— Artem Kaznatcheev
źródło

BTW Uważam, że powinieneś ograniczyć

M

$M$ do binarności, w przeciwnym razie możesz stworzyć trywialne kontrprzykłady.

— Sasho Nikolov

@SashoNikolov Co masz na myśli przez trywialne kontrprzykładów jeśli

M

$M$ nie jest

0 / 1

$0/1$ (wierzę, że myśli nad reali)?

— T ....

Na przykład problem „zgadnij mój numer”, tzn. Alice ma numer w

i Bob musi go podać. Łatwo zauważyć, że złożoność komunikacji wynosi

ale ranga macierzy wynosi

{1, \dots, N}

$\{1, \ldots, N\}$

\log N

$\log N$

1

$1$

— Sasho Nikolov,

@SashoNikolov Czy potrafisz precyzyjnie odgadnąć mój numer? Nie jestem w stanie wyobrazić sobie charakterystycznej matrycy. Alicja ma

a Bob ma

, więc jaka jest funkcja

z której definiuje się

rangi

x

$x$

y

$y$

f (x, y)

$f(x,y)$

M

$M$

1

$1$

— T ....

Funkcja

, gdzie

są

-bitowych wektorów. Jeśli definicja złożoności komunikacji wymaga, aby wartość

była określana w całości przez transkrypt protokołu (taka jest definicja w Kushilevitz-Nisan), to oczywiście złożoność wynosi

f (x, y) = x

$f(x, y) = x$

x

$x$

y

$y$

n

$n$

f

$f$

n

$n$

— Sasho Nikolov,

Hipoteza przejmuje . Spojrzenie , a . Złożoność komunikacji wynosi , ale ranga nad jest , według liniowości iloczynu wewnętrznego. $\mathbb{F}_2$ $M(x, y) = \langle x, y \rangle \bmod 2$ $x, y \in \{0, 1\}^n$ $\Omega(n)$ $M$ $\mathbb{F}_2$ $n$

— Sasho Nikolov
źródło