Kommunikationskomplexität für Produktverteilungen

Question

Im Allgemeinen für das (Zwei-Partei) Set-Disjointness-Problem für Inputs der Länge N, wissen wir, dass die Parteien $ \ omega (n) $ kommunizieren müssen . Überraschenderweise entdeckte ich heute (wenn ich richtig verstanden habe), dass dies für Produktverteilungen nicht gilt, d. H. Wenn Alice- und Bob-Inputs unabhängig von willkürlichen Verteilungen ausgewählt werden! In diesem papier , zum Beispiel bieten sie eine obere Grenze mit Kommunikationskomplexität $ \ Mathcal {O} (\ sqrt {n} \ ·} (1 / \ Epsilon)) $ , wobei $ \ epsilon $ Ist ein Fehlersbegriff für die Frage hier nicht relevant. Jetzt bin ich neugierig, ob Lücken für andere bekannte Kommunikationskomplexitätsprobleme existieren.

frage: Welche anderen bekannten Probleme zeigen eine Lücke zwischen den Kommunikationskomplexitäten, wenn man willkürliche Eingabeverteilungen und Produktverteilungen berücksichtigt. Gibt es ähnliche Ergebnisse für innere Produkte oder Kreuzungen?

Answer 1

Set Disjointness ist leichter für Produktverteilungen, da die harte Verteilung für eingestellte Discointness sehr weit davon entfernt ist, eine Produktverteilung zu sein. Was benötigen wir von einer harten Verteilung $ (x, y) $ für inneres Produkt? Wir möchten, dass jeder von $ x, y $ separat, um ziemlich zufällig zu sein, und wir wollen $ x \ cdot y $ Um größtenteils Null zu sein, sagen Sie $ X \ CDOT y $ enthält höchstens eine einzige $ 1 $ . Dies kann nicht durch eine Produktverteilung erreicht werden. Während Sie den $ X \ CDot Y $ -Einrichtung erhalten, bedeutet dies, dass jeder der beiden Eingänge sehr voreingenommen ist. Wenn Sie umgekehrt sind, sind die Eingänge $ x, y $ ganz zufällig, dann $ x \ cdot y $ haben viele $ 1 $ s.

Die innere Produktfunktion leidet nicht an derselben Frage. In der Tat scheint es, dass die schwierigste Verteilung die einheitliche Verteilung ist. Sie können eine lineare untere Grenze mit der Diskrepanzmethode beweisen. Dies ist ein Standard und verwendet eine an der Diskrepanz, die als lindsey's lemma bekannte Diskrepanz verbunden ist.

Sherstov kam mit einem optimalen Lückenbeispiel in seinem Papier Kommunikationskomplexität unter Produkt- und Nichtproduktverteilungen . Seine Funktion ist eine zufällige Funktion, die so gewählt ist, dass es keinen großen monochromatischen $ 1 $ -rectangles gibt. Das Endergebnis ist eine Funktion, deren randomisierter Kommunikationskomplexität $ \ omega (n) $ ist, aber für jede Produktverteilung ist die randomisierte Kommunikationskomplexität $ o (1) $ .