Beste Kommunikationskomplexität untere Grenze der Disjunktheit

Es ist bekannt, dass kein deterministisches Zwei-Parteien-Protokoll das Disjointness-Problem (DISJ) an Bit-Eingängen lösen kann, ohne im schlimmsten Fall Bits zu senden (siehe z. B. das Buch von Kushilevitz und Nisan). Für begrenzte Fehlerprotokoll randomisiert, unterer A gebundenen für eine Konstante , wird auch in einem Aufsatz von Samen- Razborov [Razborov92] gezeigt wurde. Meine Frage ist: $n$ $n+1$ $\delta n$ $\delta$

Was ist derzeit der bekannteste explizite Wert von (obere und untere Grenze)? $\delta$

Gibt es auch einen Glauben an den tatsächlichen Wert von ? $\delta$

[Razborov92] Alexander A. Razborov: Über die Verteilungskomplexität von Disjointness. Theor. Comput. Sci. 106 (2): 385-390 (1992) doi: 10.1016 / 0304-3975 (92) 90260-M

lower-bounds communication-complexity Danu
quelle

Kennen Sie den Inhalt dieses kürzlich erschienenen Artikels? eccc.hpi-web.de/bericht/2012/171 . Die Autoren berechnen δ genau als eine Konstante in der Nähe von 0,4827.

Yonatan N

@Yonatan Mach das eine Antwort?

Yuval Filmus

@YonatanN Mir ist dieses kürzlich erschienene Papier nicht bekannt. Vielen Dank für den Hinweis!

Danu

Seien Sie vorsichtig, n + 1 ist für deterministische Protokolle und leicht zu beweisen, spätere Arbeiten sind für zufällige!

Domotorp

Beste Kommunikationskomplexität untere Grenze der Disjunktheit

Antworten: