Deterministische Kommunikationskomplexität vs. Partitionsnummer

Hintergrund:

Betrachten Sie das übliche Zwei-Parteien-Modell der Kommunikationskomplexität, bei dem Alice und Bob Bit-Strings x und y zugewiesen bekommen und eine Boolesche Funktion f ( x , y ) berechnen müssen , wobei f : { 0 , 1 } n × { 0 , 1 } n → { 0 , 1 } .$n$$x$$y$$f(x,y)$$f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$

Wir definieren folgende Größen:

(die deterministische Kommunikationskomplexität von f ): Die minimale Anzahl von Bits, die Alice und Bob benötigen, um f ( x , y ) deterministischzu berechnen.$D(f)$$f$$f(x,y)$

(die Partitionsnummer von f ): Der Logarithmus (Basis 2) der kleinsten Anzahl monochromatischer Rechtecke in einer Partition (oder einer disjunkten Abdeckung) von { 0 , 1 } n × { 0 , 1 } n .$Pn(f)$$f$$\{0,1\}^n \times \{0,1\}^n$

Ein monochromatisches Rechteck in ist eine Teilmenge R × C, so dass f für alle Elemente von R × C den gleichen Wert annimmt (dh monochromatisch ist) .$\{0,1\}^n \times \{0,1\}^n$$R \times C$$f$$R \times C$

Beachten Sie auch, dass sich die Partitionsnummer von der "Protokollpartitionsnummer" unterscheidet, die Gegenstand dieser Frage war .

Weitere Informationen finden Sie im Text von Kushilevitz und Nisan. In ihrer Notation habe ich als log 2 C D ( f ) definiert .$Pn(f)$$\log_2 C^D(f)$

Anmerkung : Diese Definitionen können leicht auf nicht-boolesche Funktionen verallgemeinert werden , bei denen die Ausgabe von f eine größere Menge ist.$f$$f$

Bekannte Ergebnisse:

Es ist bekannt, dass eine untere Schranke von D ( f ) ist , dh für alle (Booleschen oder nicht-Booleschen) f gilt P n ( f ) ≤ D ( f ) . In der Tat sind die meisten Techniken der unteren Schranke (oder vielleicht alle?) Für D ( f ) tatsächlich die untere Schranke P n ( f ) . (Kann jemand bestätigen, dass dies für alle Techniken der unteren Schranken gilt?)$Pn(f)$$D(f)$$f$$Pn(f) \leq D(f)$$D(f)$$Pn(f)$

Es ist auch bekannt, dass diese Schranke höchstens quadratisch lose ist (für Boolesche oder nicht-Boolesche Funktionen), dh . Zusammenfassend wissen wir Folgendes:$D(f) \leq (Pn(f))^2$

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

Es wird vermutet, dass . (Dies ist das offene Problem 2.10 in Text für Text von Kushilevitz und Nisan.) Nach meinem besten Wissen ist die bekannteste Trennung zwischen diesen beiden für Boolesche Funktionen jedoch nur ein Multiplikationsfaktor von 2, wie in "The Linear-Array-Vermutung in der Kommunikationskomplexität ist falsch "von Eyal Kushilevitz, Nathan Linial und Rafail Ostrovsky.$Pn(f) = \Theta(D(f))$

Genauer gesagt weisen sie eine unendliche Familie von Booleschen Funktionen , so dass D ( f ) ≥ ( 2 - o ( 1 ) ) P n ( f ) ist .$f$$D(f) \geq (2 - o(1)) Pn(f)$

Frage:

Was ist die bekannteste Trennung zwischen und D ( f ) für nicht-boolesche Funktionen? Ist es immer noch die oben genannte Faktor-2-Trennung?$Pn(f)$$D(f)$

Hinzugefügt in Version 2 : Da ich seit einer Woche keine Antwort mehr erhalten habe, freue ich mich auch über Teilantworten, Vermutungen, Hörensagen, anekdotische Beweise usw.

Diese Frage wurde gerade gelöst! Wie gesagt, das war bekannt

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

Es war jedoch ein großes offenes Problem zu zeigen, dass entweder oder dass es eine Funktion gibt, für die P n ( f ) = o ( D ( f ) ) .$Pn(f) = \Theta(D(f))$$Pn(f) = o(D(f))$

Dies wurde vor einigen Tagen von Mika Göös, Toniann Pitassi und Thomas Watson ( http://eccc.hpi-web.de/report/2015/050/ ) gelöst . Sie zeigen, dass es eine Funktion die erfüllt$f$

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

Sie zeigen auch ein optimales Ergebnis für die einseitige Version von , die ich mit P n 1 ( f ) bezeichnen werde , wobei Sie nur die 1-Eingänge mit Rechtecken abdecken müssen. P n 1 ( f ) erfüllt ebenfalls $Pn(f)$$Pn_1(f)$$Pn_1(f)$

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

und sie zeigen, dass dies die bestmögliche Beziehung zwischen den beiden Maßen ist, da sie eine Funktion die erfüllt$f$

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

Sie bemerken, dass die unteren Schranken von eng mit allen existierenden Techniken der unteren Schranken zusammenhängen. Für Boolesche Funktionen scheint dies wahr zu sein, solange die log-rank-Vermutung wahr ist. Jedoch P n ( f ) kann exponentiell größer als der Verwirrmenge gebunden.$Pn(f)$$Pn(f)$

Mir ist nicht klar, wie sehr sich und D ( f ) im nicht-booleschen Fall unterscheiden können.$Pn(f)$$D(f)$

Im Übrigen werde ich diese Bemerkungen präzisieren.

KN (Kushilevitz und Nisan in ihrem Lehrbuch von 1997) umreißen die drei Grundtechniken für Boolesche Funktionen: Größe eines Narrensatzes, Größe eines monochromatischen Rechtecks ​​und Rang der Kommunikationsmatrix.

Erstens setzt Narren. Eine Täuschungsmenge ist monochromatisch: Es gibt einige z ∈ { 0 , 1 }, so dass f ( x , y ) = z für alle ( x , y ) ∈ S gilt . Ein letztes Patching ist dann erforderlich, um die andere Farbe zu berücksichtigen. Dieser zusätzliche Schritt kann vermieden werden. Sei f : X × Y → { 0 , 1 } eine Funktion. Ein Paar verschiedener Elemente ( x 1$S$$z \in \{0,1\}$$f(x,y) = z$$(x,y)\in S$$f \colon X \times Y \to \{0,1\}$ istschwach foolingfür f , wenn f ( x 1 , y 1 ) = f ( x 2 , y 2 ) impliziertdass entweder f ( x 1 , y 2 ) ≠ f ( x 1 , y 1 ) oder 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)$ . Eine Menge S ⊆ X × Y ist eineschwache Täuschungsmengefür f, wenn jedes einzelne Paar von Elementen von S schwach täuscht. KN besagt implizit nach dem Beweis von 1.20, dass die Protokollgröße einer schwachen Täuschungsmenge eine Untergrenze für die Kommunikationskomplexität ist.$f(x_2,y_1) \ne f(x_1,y_1)$$S \subseteq X \times Y$$f$$S$

Ein größter schwacher Narrensatz wählt ein repräsentatives Element aus jedem monochromen Rechteck in einem kleinsten nicht zusammenhängenden Satzdeckel aus. Die Größe eines größten schwachen Narrensatzes ist daher höchstens so groß wie (der Exponent von) der Partitionsnummer. Leider ist die durch Täuschungssets bereitgestellte Schranke oft schwach. Der Beweis von KN 1.20 zeigt, dass jede Funktion, die jedes Element eines schwachen Narrensatzes S auf ein monochromatisches Rechteck R s abbildet, das dieses Element enthält, injektiv ist. Es kann jedoch viele monochromatische Rechtecke R in einer kleinsten disjunkten Abdeckung geben, die nicht im Bild von S erscheinen , wobei jedes Element von R mit einigen, aber nicht allen Elementen von R schwach täuscht$s$$S$$R_s$$R$$S$$R$ und kann daher nicht einfach zu S hinzugefügt werden. Tatsächlich Dietzfelbinger zeigte Hromkovic und Schnitger (doi:10.1016 / S0304-3975 (96) 00062-X)die für alle groß genug n mindestens 1 / 4 aller Booleschen Funktionen auf n Variablen P n ( f ) = n haben noch (schwache) Narrenmengen von Log-Größe O ( log n ) . Das Protokoll der Größe eines größten (schwachen) Narrensatzes kann also exponentiell kleiner sein als die Kommunikationskomplexität.$S$$S$$n$$1/4$$n$$Pn(f) = n$$O(\log n)$

Für den Rang würde das Herstellen einer engen Entsprechung zwischen dem Rang der Matrix der Funktion und ihrer Partitionsnummer eine Form der Log-Rang-Vermutung herstellen (abhängig von der Enge der Entsprechung). Wenn es zum Beispiel eine Konstante so dass P n ( f ) ≤ ein log r k ( f ) für jede Boolesche Funktion f ist , dann ist D ( f ) ≤ ( 2 ein log r k ( f ) ) $a> 0$$Pn(f) \le a\log rk(f)$$f$$D(f) \le (2a\log rk(f))^2$und dann gilt eine Art logarithmische Rang-Vermutung für Familien von Funktionen, für die letztendlich mit | zunimmt X | + | Y | , Mit dem Exponenten 2 + ε für jedes ε > 0 erreichbar für hinreichend große | X | + | Y | . (Erinnern wir uns, dass die Lovász-Saks-log-rank-Vermutung besagt, dass es eine Konstante c > 0 gibt, so dass D ( f ) ≤ ( log $rk(f)$$|X|+|Y|$$2+\epsilon$$\epsilon > 0$$|X|+|Y|$$c>0$ für jede Boolesche Funktion f ; hier ist r k ( f ) der Rang der Kommunikationsmatrix von f über den Real.)$D(f) \le (\log rk(f))^c$$f$$rk(f)$$f$

Wenn es nur ein recht großes monochromatisches Rechteck zusammen mit vielen kleinen gibt, ergibt die Partitionsnummer eine stärkere Grenze als die Protokollgröße eines größten monochromatischen Rechtecks. Die log-rank-Vermutung entspricht jedoch auch einer Vermutung über die Größe eines größten monochromatischen Rechtecks ​​(Nisan und Wigderson 1995, doi: 10.1007 / BF01192527 , Theorem 2). Die Verwendung von monochromatischen Rechtecken ist derzeit nicht als identisch mit der Verwendung der Partitionsnummer bekannt, sie hängen jedoch eng zusammen, wenn die log-rank-Vermutung zutrifft.

Zusammenfassend kann die Protokollgröße eines größten Satzes schwacher Narren exponentiell kleiner als die Partitionsnummer sein. Es kann Lücken zwischen den anderen Techniken der unteren Schranke und der Partitionsnummer geben, aber wenn die Log-Rang-Vermutung gilt, sind diese Lücken klein.

Durch die Verwendung von Größenbegriffen, die den üblichen (der Kardinalität) erweitern, kann die Größe eines monochromatischen Rechtecks ​​zur Verallgemeinerung von Täuschungssätzen und zur Verringerung der Kommunikationskomplexität verwendet werden (siehe KN 1.24). Ich bin nicht sicher, wie nahe die verallgemeinerte größte "Größe" eines monochromatischen Rechtecks ​​an der Kommunikationskomplexität liegen muss.

$D(f)$$\log rk(f)$$f$$\log n$$3^n$$D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$$D(f)$$Pn(f)$$2.5$$Pn(f)$$D(f)$$f$

$Pn(f)$