Testen auf Positivität statt auf Gleichheit

Alice und Bob haben n-Bit-Zeichenfolgen und möchten herausfinden, ob sie gleich sind, während sie wenig kommunizieren. Die randomisierte Standardlösung besteht darin, die n-Bit-Zeichenfolgen als Polynome des Grades und dann die Polynome über einige zufällig ausgewählte Elemente aus einem Feld mit einer Größe größer als auszuwerten . Dies erfordert eine Kommunikation . $n$ $n$ $O(\log |F|)$

Angenommen, wir legen stattdessen eine lexikografische Reihenfolge für die Zeichenfolgen fest und möchten stattdessen ermitteln, welche Zeichenfolge "größer" ist. Dies entspricht der Ermittlung des äußersten linken Bits, in dem sich die Zeichenfolgen unterscheiden.

Gibt es dafür ein ähnliches randomisiertes Protokoll oder eine bekannte Untergrenze? Dies scheint sich auf das Testen der Positivität von Polynomen zu beziehen.

ps Während die lexikografische Reihenfolge am offensichtlichsten zu sein scheint, kann ich andere Ordnungen in Ordnung bringen: Für den Zweck, an dem ich interessiert bin, ist alles, was wir brauchen, eine Ordnung.

communication-complexity property-testing Suresh Venkat
quelle

Ich dachte, die standardmäßige zufällige Lösung wäre, eine zufällige lineare Kombination der Bits auszuwählen und einfach die resultierende Parität zu senden, für die nur -Kommunikation erforderlich ist.

O (1)

$O(1)$

Joshua Grochow

@JoshuaGrochow Ich denke, das hängt von der Art des Zufalls ab - öffentlich oder privat. Das von Ihnen erwähnte Protokoll verwendet öffentliche Zufälligkeit.

Sasho Nikolov

Zum Vergleich ist es vielleicht erwähnenswert, dass die deterministische Komplexität , so dass das triviale Protokoll optimal ist. Dies ergibt eine schöne exponentielle Lücke zwischen deterministischen / exakten und randomisierten Lösungen, was zeigt, dass (zumindest in Bezug auf die Kommunikationskomplexität) Zufälligkeit wirklich helfen kann.

n + 1

$n+1$

András Salamon

Hm ja. Wie viel Kommunikation wird für einen Algorithmus benötigt, der niemals die falsche Antwort gibt und für alle Eingabepaare MÖGLICHERWEISE mit einer Wahrscheinlichkeit von höchstens 1/2 für dieses Eingabepaar ist?

$\:$

Vielleicht ist es erwähnenswert, dass die Komplexität der runden Kommunikation größer als dh sie ist linear für , siehe arxiv.org/ abs / cs / 0309033 . Es ist eine schöne Zeitung :)

k

$k$

Ω (n^{1 / k} k^{- 2})

$\Omega(n^{1/k}k^{-2})$

k = 1

$k=1$

Marc Bury

Antworten:

Dies ist als Mehr-als-Problem bei der Kommunikationskomplexität bekannt. Es existiert ein Algorithmus mit -Kommunikationskomplexität (Aufgabe 3.18 im Nisan-Kushilevitz-Buch). $O(\log n)$

Bearbeiten: Der Algorithmus stammt von Nisan (Seite 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

Es verwendet den von @Sasho Nikolov unten vorgeschlagenen Ansatz - Ausführen einer binären Suche unter Verwendung von Gleichheitstests mit konstantem Fehler, um die Vergleiche durchzuführen. Dies kann mit Abfragen unter Verwendung des "noisy binary search algorithm" von Feige, Peleg, Raghavan und Upfal erfolgen: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf $O(\log n)$

Um ein (nicht explizites) privates Zufallsprotokoll zu erhalten, kann man das Ergebnis von Newman anwenden: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf

Grigory Yaroslavtsev
quelle

\log n

$\log n$

O (1)

$O(1)$

O (\log n \log \log n)

$O(\log n \log \log n)$

O (1 / \log n)

$O(1 / \log n)$

O (\log \log n)

$O(\log \log n)$

@SashoNikolov Ok, ich denke, so etwas kann als "verrauschte binäre Suche" verwendet werden, die einen konstanten Bruchteil von Fehlern toleriert, so dass wir bei den Gleichheitstests eine konstante Fehlerwahrscheinlichkeit verwenden können: dl.acm.org/citation.cfm? id = 167129

Grigory Yaroslavtsev

wahr. Ich meinte binäre Suche, bei der jeder Vergleich mit geringer konstanter Wahrscheinlichkeit das falsche Ergebnis liefern kann. Ich denke, dieses Papier liefert das benötigte Ergebnis, zum Beispiel: dl.acm.org/citation.cfm?id=100230

Sasho Nikolov

Verschob die Diskussion in die Antwort.

Grigory Yaroslavtsev

Siehe Die Kommunikationskomplexität der Addition .

$O(\log n)$

Manu
quelle