Beste Kommunikationskomplexität untere Grenze der Disjunktheit

14

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:nn+1δnδ

Was ist derzeit der bekannteste explizite Wert von (obere und untere Grenze)?δ

Gibt es auch einen Glauben an den tatsächlichen Wert von ?δ

[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

Danu
quelle
7
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
2
@Yonatan Mach das eine Antwort?
Yuval Filmus
@YonatanN Mir ist dieses kürzlich erschienene Papier nicht bekannt. Vielen Dank für den Hinweis!
Danu
4
Seien Sie vorsichtig, n + 1 ist für deterministische Protokolle und leicht zu beweisen, spätere Arbeiten sind für zufällige!
Domotorp

Antworten:

16

δ

Die Konstante selbst wurde mit einem Computer-Algebra-System gefunden und kann meines Wissens nicht einfach ausgedrückt werden.

Yonatan N
quelle