Jaka jest największa różnica między rangą a przybliżoną rangą?

Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy. A co z różnicą między rangą a przybliżoną rangą macierzy boolowskiej?

— pyao
źródło

jaka jest „przybliżona pozycja” matrycy?

— Suresh Venkat,

-approximate rangi logiczną macierz jest minimalny stopień prawdziwej macierzy , który różni się od co najwyżej w dowolnej pozycji (por Buhrman i Wolf 2001 „Komunikat złożoność dolne granice wielomianami”). Przydałoby się edytować pytanie, aby to wyjaśnić (jeśli jest to pożądana definicja) i opisać rolę (ponieważ różnica w poziomach wyraźnie zależy od ).

ϵ

$\epsilon$

M

$M$

A

$A$

M

$M$

ϵ

$\epsilon$

ϵ

$\epsilon$

ϵ

$\epsilon$

— mjqxxxx

Najpierw dam trochę tła i zdefiniuję przybliżoną rangę. Dobrym odniesieniem jest niedawna ankieta przeprowadzona przez Lee i Schraibmana w Lower Bounds na temat złożoności komunikacji .

Definicja: Niech będzie macierzą znaków. Przybliżona ranga ze współczynnikiem aproksymacji , oznaczona , wynosi $A$ $A$ $\alpha$ $rank^\alpha(A)$

$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \alpha} rank(B)$ .

Kiedy , zdefiniuj $\alpha\to \infty$

$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j]} rank(B)$ .

Wynik Krause mówi, że gdzie i to złożoność komunikacji prywatnej monety ograniczonego błędu z błędem ograniczonym przez . $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ $\alpha=1/(1-2\epsilon)$ $R_\epsilon^{pri}$ $A$ $\epsilon$

Powyżej było w tle. Teraz, aby odpowiedzieć na pytanie, Paturi i Simon pokazali, że całkowicie charakteryzuje złożoność komunikacji z nieograniczonym błędem . Wykazali oni również, że to zgadza się z wymiarem minimalnym wykonania układu realizującego funkcję logiczną, której matryca komunikacji . Złożoność komunikacji funkcji nieograniczonego błędu funkcji równości wynosi . Miej to w pamięci. $rank^\infty(A)$ $A$ $A$ $O(1)$

Macierz komunikacji dla równości jest tylko tożsamością, tj. Boolowska macierz z rzędami i kolumnami ze wszystkimi na przekątnej. Oznaczmy to jako . Alon wykazał, że która jest ścisła do współczynnika logarytmicznego (z twierdzeniem Krausea otrzymujemy ). $2^n$ $2^n$ $I_{2^n}$ $rank^2(I_{2^n})=\Omega(n)$ $R_\epsilon^{pri}(EQ)=\Omega(\log n)$

Macierz tożsamości ma pełną rangę, tj. . Mamy więc wykładniczo duże separacje dla i . $2^n$ $\alpha=2$ $\alpha\to\infty$

— Marcos Villagra
źródło

Dzięki. ale moje pytanie brzmi, czy istnieje nadprzewidziana luka dla i , gdzie ale nie .

r a n k (A)

$rank(A)$

r a n k^{α} (A)

$rank^{\alpha}(A)$

α > 1

$\alpha>1$

α \neq \infty

$\alpha\neq\infty$

— pyao

Ach, rozumiem, ale nie jest to zapisane w pytaniu. Według mojej wiedzy największa luka ma charakter wykładniczy.

— Marcos Villagra

Marcos podaje odniesienie, które pokazuje odstęp pomiędzy i . jak może występować przerwa nadwykładnicza, gdy rozmiar macierzy wynosi ?

2^{n} / n

$2^n/n$

r a n k

${rank}$

{r a n k}^{2}

${rank}^2$

2^{n}

$2^n$

— Sasho Nikolov

masz na myśli lukę zamiast ?

Ω (2^{n})

$\Omega(2^n)$

2^{Ω (n)}

$2^{\Omega(n)}$

— Sasho Nikolov

Sasho ma rację, co masz na myśli przez „super wykładniczy? W przypadku każdego problemu z komunikacją, macierz jest zawsze ponad .

{0, 1}^{n} \times {0, 1}^{n}

$\{0,1\}^n \times \{0,1\}^n$

— Marcos Villagra