Einweg randomisierte Kommunikationskomplexität der Disjunktheit

Ich suche eine Referenz für die (klassische) einseitig randomisierte Kommunikationskomplexität der Disjunktheit, wenn das Universum groß sein kann. Angenommen, Alice und Bob haben beide Mengen der Größe $m$ aus einem Universum der Größe $U$ und Bob möchte feststellen, ob der Schnittpunkt ihrer Mengen leer ist oder nicht. Ich würde prob Fehler wie $<1/3$ , sagen.

Ich kann die Untergrenze des Standard- $\Omega(m)$ -Bits finden und einige Arbeiten zur Komplexität der bidirektionalen Kommunikation durchführen. Gibt es jedoch eine Referenz für etwas engeres für die bidirektionale Kommunikation?

EDIT: Ich hätte angeben sollen, dass ich mich für das Modell der privaten Zufälligkeit (nicht der öffentlichen Münze) interessiere.

cc.complexity-theory reference-request lower-bounds communication-complexity Raphael
quelle

Werden die Sets zufällig ausgewählt oder nur die Kommunikationsstrategie?

mjqxxxx

Die Randomisierung bezieht sich nur auf die Tatsache, dass Alice und Bob zufällige Bits verwenden dürfen.

Raphael

Denken Sie wirklich über eine Einwegkommunikation (Alice sendet eine Nachricht an Bob, der dann die Antwort ausgibt) oder eine "gleichzeitige" Kommunikation (Alice und Bob senden jeweils eine Nachricht an einen Schiedsrichter, der die Antwort ankündigt) in Betracht. Im ersteren Fall öffentlich und privat Zufälligkeit ist die gleiche und so scheint es, dass die Antworten unten (dh Mihais Blog) die Frage regeln.

Noam

Es ist der frühere Fall der Einwegkommunikation, wie Sie ihn definieren, an dem ich interessiert bin. Ich hoffe auf etwas Enges über den gesamten Bereich der Universumsgrößen. Wenn ich das richtig verstehe, gibt uns Mihais Beitrag eine Obergrenze von

und wir haben eine Untergrenze von die noch vorhanden ist hinterlässt eine Lücke.

O (m \log m + \log U)

$O(m \log{m} + \log{U})$

min ((\binom{U}{m}), m \log m)

$\min(\binom{U}{m}, m\log{m})$

Raphael

Ich meine natürlich .

Ω (min (\log (\binom{U}{m}), m \log m))

$\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$

Raphael

Antworten:

Die Antwort lautet . Im öffentlichen Münzenmodell haben wir (wie oben beschrieben) . Wie Yuval oben vorgeschlagen hat, benötigen wir für die Obergrenze im Modell der privaten Münzen nur ein Additiv Bits (siehe Satz 3.14 im K & N-Buch ). Dabei ist die Länge der Codierung der Eingabe ( ). Für die zusätzliche Untergrenze von im privaten Münzmodell reicht es aus, sich auf den Fall zu konzentrieren (da die anderen Elemente so festgelegt werden können, dass sie alle unterschiedlich sind) nur die Gleichheitsfunktion auf $\Theta(m\log m + \log\log |U|)$ $\Theta(m\log m)$ $O(\log n)=O(\log m + \log\log |U|)$ $n$ $n=m\log|U|$ $\Omega(\log\log |U|)$ $m=1$ $\log |U|$ -bit-Strings, deren private Münzkomplexität darin logarithmisch ist (Beispiel 3.9 in K & N).

Noam
quelle

Danke, das ist perfekt, aber wir müssen es nicht auch mit das kleiner als je nachdem, wie sich auf bezieht . Im Extremfall, wenn , muss Alice nicht viel sagen.

\log (\binom{U}{m})

$\log {\binom{U}{m}}$

m \log m

$m\log{m}$

U

$U$

m

$m$

U = m

$U=m$

Raphael

Ja, dies ist für großes (mindestens ), andernfalls schlägt die in Mihais Beitrag erwähnte Untergrenze fehl.

U

$U$

m^{1 + ϵ}

$m^{1+\epsilon}$

Noam

Damit ist die Frage geklärt :-)

Marcos Villagra

Übrigens wollte ich Sie immer fragen, warum die allgemeine Untergrenze von im K & N-Buch enthalten? Es würde automatisch Dinge wie Satz 3.9 implizieren.

\log \log | X | \leq R (f)

$\log \log |X| \le R(f)$

Domotorp

Ist bekannt / offensichtlich, dass für kleinere Universumsgrößen eng ist? Sagen Sie zum Beispiel .

\log (\binom{U}{m})

$\log{\binom{U}{m}}$

U = m \log m

$U = m \log{m}$

Raphael

Für eine beliebige Anzahl von Runden ist die Untergrenze der Disjunktheit (vgl. Die probabilistische Kommunikationskomplexität der Mengenschnittstelle. SIAM J. Discrete Math. Band 5, Ausgabe 4, S. 545-557 (November 1992) ). . $\Omega(n)$

Für 1-way, Kremer, Nisan und Ron hat gezeigt , dass für jeden gegebenen , , wobei die 1- randomisiert ist Art und Weise Kommunikationskomplexität von mit Fehler , und ist die VC-Dimension von . Dann haben wir . Tatsächlich gibt es jedoch eine enge Untergrenze für DISJ, nämlich (vgl. Mihai Patrascus Blog ). $f$ $R_\epsilon^1(f)=\Omega(VC(f))$ $R_\epsilon^1(f)$ $f$ $\epsilon$ $VC(f)$ $f$ $VC(DISJ)=n$ $\Omega(n\log n)$

Marcos Villagra
quelle

Mihai Patrascus Blog sagt, dass auch für große Universen mit der Verwendung einer universellen Hash-Funktion erreichbar ist. Dies ist sinnvoll, wenn Alice und Bob eine gemeinsame Zufallsquelle haben. Aber wenn sie unabhängige Quellen haben, muss Alice Bob dann nicht sagen, welche Hash-Funktion sie verwendet? Wie viel Platz braucht das?

O (n \log n)

$O(n\log n)$

mjqxxxx

Es gibt einen Trick, der zeigt, dass öffentliche Zufälligkeit mit privater Zufälligkeit identisch ist: Verwenden Sie eine Chernoff-Grenze, um zu zeigen, dass ein Probenraum mit Polynomgröße [im Logarithmus der Anzahl möglicher Eingaben] vorhanden ist, der die Erfolgswahrscheinlichkeit "gut genug" annähert. an allen Eingängen; Alice wählt einen dieser Punkte aus und sendet seinen logarithmischen Index an Bob. Dieser Trick gilt in diesem Fall nicht direkt (da es unendlich viele Eingaben gibt), kann aber plausibel irgendwie angepasst werden.

Yuval Filmus

Vielen Dank! Ich hätte private Zufälligkeit in der Frage angeben sollen. Jetzt reparieren.

Raphael

Die zufällige Komplexität der privaten Münze (Ein- und Zweiwege) einer beliebigen Funktion ist mindestens, z. B. in Ihrem Fall mindestens , was wenn klein ist, was eine bessere Untergrenze ergeben kann. Dieses Ergebnis wird in Yaos wegweisender Arbeit über CC erwähnt. Den Beweis finden Sie in meiner Masterarbeit, Lemma 3.8 und Umgebung: http://www.cs.elte.hu/~dom/cikkek/szakdolgozat.pdf $\log \log |\text{size}|$ $\log \log {U \choose m}$ $\log \log U$ $m$

Natürlich ist dies eine gerade untere Grenze, vielleicht ein passender ihre obere wie gebunden ist . $m + \log \log U$

domotorp
quelle