Deterministyczna złożoność komunikacji a numer partycji

Tło:

Rozważmy modelu zwykłe dwie grupy komunikacji złożoności gdzie Alicja i Bob podane $n$ -bitowe łańcuchy $x$ i $y$ i muszą oblicz logiczna funkcja $f(x,y)$ , gdzie $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ .

Definiujemy następujące ilości:

$D(f)$ (deterministyczna złożoność komunikacji$f$ ): Minimalna liczba bitów, które Alice i Bob muszą przekazać, aby obliczyć$f(x,y)$ deterministycznie.

$Pn(f)$ (numer podziału$f$ ): Logarytm (podstawa 2) najmniejszej liczby monochromatycznych prostokątów w przegrodzie (lub rozłącznej pokrywie) o wartości$\{0,1\}^n \times \{0,1\}^n$ .

Monochromatyczną prostokąt $\{0,1\}^n \times \{0,1\}^n$ jest podzbiorem $R \times C$ , tak że $f$ przyjmuje tę samą wartość (to jest monochromatyczne) na wszystkich elementach $R \times C$ .

Zauważ też, że numer partycji różni się od „numeru partycji protokołu”, który był przedmiotem tego pytania .

Aby uzyskać więcej informacji, zobacz tekst Kushilevitza i Nisana. W ich zapisu, co I określa się $Pn(f)$ wynosi $\log_2 C^D(f)$ .

Uwaga : Definicje te można łatwo uogólnić na funkcje inne niż boolowskie $f$ , gdzie wyjście $f$ jest jakimś większym zestawem.

Znane wyniki:

Wiadomo, że $Pn(f)$ ma dolną granicę $D(f)$ , to znaczy dla wszystkich (binarnej bądź nie-logiczna), $f$ , $Pn(f) \leq D(f)$ . Faktycznie, większość obniżyć techniki bound (albo wszystkie?) Dla $D(f)$ w rzeczywistości dolna granica $Pn(f)$ . (Czy ktoś może potwierdzić, że dotyczy to wszystkich technik o niższych granicach?)

Wiadomo również, że granica ta jest co najwyżej kwadratowo luźna (dla funkcji boolowskich lub nie-boolowskich), tj. . Podsumowując, wiemy, co następuje:$D(f) \leq (Pn(f))^2$

$Pn(f) \leq D(f) \leq (Pn(f))^2$

Przypuszcza się, że . (Jest to otwarty problem 2.10 w tekście po tekście Kushilevitza i Nisana.) Jednak, zgodnie z moją najlepszą wiedzą, najbardziej znany rozdział między tymi dwiema funkcjami boolowskimi jest tylko mnożnikiem 2, jak pokazano w „The Hipotezy o liniowej macierzy w złożoności komunikacyjnej są fałszywe ”Eyala Kushilevitza, Nathana Liniala i Rafaila Ostrovsky'ego.$Pn(f) = \Theta(D(f))$

Dokładniej, wykazują nieskończoną rodzinę funkcji boolowskich , tak że D ( f ) ≥ ( 2 - o ( 1 ) ) P n ( f ) .$f$$D(f) \geq (2 - o(1)) Pn(f)$

Pytanie:

Co jest najlepiej znanym oddzielenie i D ( f ) dla funkcji niż logiczna? Czy nadal jest to wyżej wymieniony czynnik 2?$Pn(f)$$D(f)$

Dodano w wersji 2 : Ponieważ nie otrzymałem odpowiedzi od tygodnia, cieszę się również z częściowych odpowiedzi, przypuszczeń, pogłosek, anegdotycznych dowodów itp.

To pytanie zostało właśnie rozwiązane! Jak wspomniałem, było to znane

,$Pn(f) \leq D(f) \leq (Pn(f))^2$

ale głównym problemem otwartym było wykazanie, że lub że istnieje funkcja, dla której P n ( f ) = o ( D ( f ) ) .$Pn(f) = \Theta(D(f))$$Pn(f) = o(D(f))$

Kilka dni temu rozwiązali to Mika Göös, Toniann Pitassi, Thomas Watson ( http://eccc.hpi-web.de/report/2015/050/ ). Pokazują, że istnieje funkcja która spełnia$f$

.$Pn(f) = \tilde{O}((D(f))^{2/3})$

Pokazują również optymalny wynik dla jednostronnej wersji , którą oznaczę jako P n 1 ( f ) , w której wystarczy pokryć 1-wejściowe prostokąty. P n 1 ( f ) również spełnia $Pn(f)$$Pn_1(f)$$Pn_1(f)$

,$Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$

i pokazują, że jest to najlepsza możliwa relacja między dwoma miarami, ponieważ spełniają one funkcję która spełnia$f$

.$Pn_1(f) = \tilde{O}((D(f))^{1/2})$

Zauważasz, że dolne granice na są ściśle powiązane ze wszystkimi istniejącymi technikami dolnych granic . W przypadku funkcji boolowskich wydaje się to prawdą, pod warunkiem, że hipoteza log-rank jest prawdziwa. Jednakże P n ( f ) może być gwałtownie większa niż nastawiona Fooling związana.$Pn(f)$$Pn(f)$

To nie jest dla mnie jasne, ile i D ( f ) może się różnić w przypadku nie-logicznej.$Pn(f)$$D(f)$

W pozostałej części dopracowuję te komentarze.

KN (Kushilevitz i Nisan w swoim podręczniku z 1997 r.) Przedstawiają trzy podstawowe techniki funkcji boolowskich: rozmiar zestawu do oszukiwania, rozmiar monochromatycznego prostokąta oraz stopień matrycy komunikacyjnej.

Po pierwsze, oszukiwanie zestawów. Zestaw oszukiwanie jest monochromatyczne: jest kilka z ∈ { 0 , 1 } , tak że F ( x , y ) = oo o co ( x , y ) ∈ S . Konieczne jest zakończenie poprawki, aby uwzględnić inny kolor. Tego dodatkowego kroku można uniknąć. Niech f : X × Y → { 0 , 1 } będzie funkcją. Para różnych elementów ( x 1$S$$z \in \{0,1\}$$f(x,y) = z$$(x,y)\in S$$f \colon X \times Y \to \{0,1\}$ jestsłabo oszukiwaniena f , jeśli f ( x 1 , Y 1 ) = f ( x 2 , Y 2 ) wynika, że zarówno f ( x 1 , Y 2 ) ≠ f ( x 1 , y 1 ) lub f $(x_1,y_1),(x_2,y_2) \in X \times Y$$f$$f(x_1,y_1) = f(x_2,y_2)$$f(x_1,y_2) \ne f(x_1,y_1)$ . Zestaw S ⊆ X × Y jestsłabym zestawemdooszukiwaniadla f, jeśli każda wyraźna para elementów S słabo oszuka. KN niejawnie stwierdza po dowodzie 1,20, że rozmiar dziennika słabego zestawu do oszukiwania stanowi dolną granicę złożoności komunikacji.$f(x_2,y_1) \ne f(x_1,y_1)$$S \subseteq X \times Y$$f$$S$

Największy słaby zestaw wygłupów wybiera reprezentatywny element z każdego monochromatycznego prostokąta w najmniejszej rozłącznej pokrywie zestawu. Rozmiar największego zestawu słabego oszukiwania jest zatem co najwyżej tak duży jak (wykładnik) numeru partycji. Niestety granice zapewniane przez zestawy do oszukiwania są często słabe. Dowód KN 1.20 wykazuje, że każdy z elementów odwzorowujących funkcję słabego zestaw oszukiwanie S do monochromatyczne prostokąt R s zawierającego ten element jest za pomocą wstrzyknięć. Jednak może istnieć wiele monochromatycznych prostokątów R w najmniejszej rozłącznej osłonie, które nie pojawiają się na obrazie S , przy czym każdy element R słabo oszukiwa w przypadku niektórych, ale nie wszystkich elementów$s$$S$$R_s$$R$$S$$R$ , a więc nie może być po prostu dodany do S . W rzeczywistości Dietzfelbinger, Hromkovič i Schnitger wykazały (doi:10,1016 / S0304-3975 (96) 00062-X), które wszystkie wystarczająco dużą n , co najmniej 1 / 4 wszystkich funkcji logicznych w n zmienne P n ( f ) = N jeszcze mają (słabe) zestawy do oszukiwania log-size O ( log n ) . Zatem dziennik wielkości największego (słabego) zestawu do oszukiwania może być wykładniczo mniejszy niż złożoność komunikacji.$S$$S$$n$$1/4$$n$$Pn(f) = n$$O(\log n)$

W przypadku rangi ustanowienie ścisłej zgodności między rangą macierzy funkcji a jej numerem podziału ustaliłoby formę domniemania log-rank (w zależności od ścisłości korespondencji). Na przykład, jeśli istnieje stała taka, że P n ( f ) ≤ a log r k ( f ) dla każdej funkcji boolowskiej f , to D ( f ) ≤ ( 2 a log r k ( f ) ) $a> 0$$Pn(f) \le a\log rk(f)$$f$$D(f) \le (2a\log rk(f))^2$I rodzajem log-rank przypuszczeń następnie zachodzi dla rodziny funkcji, dla których ostatecznie zwiększa się | X | + | Y | , z wykładnikiem 2 + ϵ dla dowolnego ϵ > 0 osiągalnego dla wystarczająco dużych | X | + | Y | . (Przypomnijmy, że hipoteza logarytmicznej rangi Lovásza-Saksa mówi, że istnieje stała c > 0 taka, że D ( f ) ≤ ( log $rk(f)$$|X|+|Y|$$2+\epsilon$$\epsilon > 0$$|X|+|Y|$$c>0$ dla każdej funkcji boolowskiej f ; tutaj r k ( f ) to ranga macierzy komunikacyjnej f nad rzeczywistymi.)$D(f) \le (\log rk(f))^c$$f$$rk(f)$$f$

Podobnie, jeśli istnieje tylko jeden dość duży monochromatyczny prostokąt wraz z wieloma małymi, wówczas numer podziału daje silniejsze powiązanie niż rozmiar logarytmiczny największego monochromatycznego prostokąta. Jednak przypuszczenie rang logarytmicznych jest również równoważne przypuszczeniu o wielkości największego monochromatycznego prostokąta (Nisan i Wigderson 1995, doi: 10.1007 / BF01192527 , Twierdzenie 2). Zatem używanie prostokątów monochromatycznych nie jest obecnie znane jako „to samo co” przy użyciu numeru podziału, ale są one ściśle powiązane, jeśli utrzymuje się domniemanie log-rank.

Podsumowując, rozmiar dziennika największego zestawu słabego oszukiwania może być wykładniczo mniejszy niż numer partycji. Mogą istnieć luki między innymi dolnymi granicami technik a numerem podziału, ale jeśli hipoteza log-rank utrzymuje się, to luki te są małe.

Stosując pojęcia wielkości, które rozszerzają zwykły (liczności), rozmiar dowolnego monochromatycznego prostokąta można wykorzystać do uogólnienia zestawów oszukiwania i do ograniczenia złożoności komunikacji (patrz KN 1.24). Nie jestem pewien, jak blisko uogólnionej największej „wielkości” dowolnego monochromatycznego prostokąta musi być złożoność komunikacji.

W przeciwieństwie do powyższej dyskusji dla funkcji logicznych, dla funkcji logicznych niż odstęp między i log r k ( f ) może być wykładnicza. KN 2.23 podaje przykład: niech f będzie funkcją, która zwraca rozmiar przecięć zbiorów reprezentowanych przez dwa wejściowe wektory charakterystyczne. Dla tej funkcji log-rank to log n . Teraz zestaw wszystkich par zbiorów nie przecinających się ma 3 n elementów. O ile mi wiadomo, nie może być żadnych monochromatycznych prostokątów większych niż ten zestaw. Jeśli jest to poprawne, to D ( f ) $D(f)$$\log rk(f)$$f$$\log n$$3^n$ , więc dla tej funkcji D ( f ) , P n ( f ) i wielkość logarytmiczna największego monochromatycznego prostokąta są w granicach większośćz siebie 2,5 , będąc wykładniczo daleko od rangi dziennika. Stąd małe odstępy między P n ( f ) i D ( f $D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$$D(f)$$Pn(f)$$2.5$$Pn(f)$$D(f)$może być możliwe w przypadku nie-boolowskim, ale nie są one w oczywisty sposób powiązane z log-rank macierzy . Nie znam żadnych opublikowanych prac omawiających, w jaki sposób te środki są powiązane w sprawie innej niż logiczna.$f$

Wreszcie Dietzfelbinger i in. zdefiniowano także powiązany rozszerzony zestaw oszukiwania, uogólniając warunek oszukiwania od par (podzbiory „rzędu 1”) do większych podzbiorów elementów monochromatycznych; warunki przedłużonego oszukiwania wymagają, aby submatrix połączony z elementami monochromatycznymi nie był monochromatyczny. Nie jest jasne, jak się to zachowuje, gdy zwiększa się kolejność monochromatycznych podzbiorów, ponieważ należy podzielić rozmiar rozszerzonego zestawu oszukiwania przez zamówienie i rozważyć największą wartość ze wszystkich zamówień. Jednak pojęcie to kończy się bliski dolna granica na .$Pn(f)$