Untergrenzen für nichtdeterministische Mehrparteienkommunikation

11

Dies ist eine Fortsetzung meiner vorherigen Frage zur Kommunikationsuntergrenze für partielle Boolesche Funktionen .

Kann jemand einen Hinweis auf Untergrenzen für nichtdeterministische Mehrparteienkommunikation vorschlagen? Ich habe die Arbeiten auf dem Gebiet untersucht, aber jeder scheint Trennungen des folgenden Typs aufzuweisen: eine Untergrenze für ein randomisiertes Protokoll und eine (kleinere) Obergrenze für ein nicht deterministisches Protokoll. Siehe zum Beispiel David, Pitassi und Viola 2009 , Gavinsky und Sherstov 2010 , Beame, David, Pitassi und Woelfel 2010 .

Insbesondere würde ich gerne wissen, ob es eine Norm gibt (z. B. für k Parteien), die die nichtdeterministische Mehrparteienkommunikation entweder im Modell "Nummer in der Stirn" oder "Nummer in der Hand" unterbindet.γkk

Marcos Villagra
quelle
soll ich den Bearbeitungsteil als Antwort setzen und eine andere Frage stellen?
Marcos Villagra
Sie sollten das neue Ergebnis, das Sie gefunden haben, in eine Antwort einfügen. (Vielleicht bekommst du ein Selbstlernabzeichen!) Was das neue Problem betrifft, ist es in Ordnung, es in derselben Frage zu belassen.
Hsien-Chih Chang 7 之
Ich denke, es ist in Ordnung, es als Antwort hinzuzufügen. Sie haben die Frage vor einiger Zeit gestellt und auf Antworten gewartet. Sie haben dann eine gefunden - genau dafür ist das Selbstlernabzeichen gedacht
Suresh Venkat

Antworten:

4

Nach langem Lesen habe ich das folgende Papier gefunden

Troy Lee und Adi Shraibman. Disjunktion ist im Mehrparteien-Modell auf der Stirn schwer . In Proceedings of IEEE 23. Jahreskonferenz über Computerkomplexität . 22. bis 26. Juni 2008.

μα

k0ϵ<1/2Rϵk(M)log(μα(M))log(αϵ)αϵ=1/(12ϵ)ααϵ

Dann machen sie die folgende Bemerkung.

logμ

αMμ(M)=1/Disc(M)Disc(M)MkΩ(logn/(k1))Ω(n1/(k+1)22k)μα

Gibt es eine andere Norm, die stärker ist als die Diskrepanz, die für untere Grenzen in der nichtdeterministischen Mehrparteienkommunikation verwendet werden kann? Oder ist es eng? Diese Ergebnisse sind sehr aktuell, daher ist dies möglicherweise ein offenes Problem. Das Follow-up zu dieser Frage ist hier .

Marcos Villagra
quelle
Sie können Ihre eigene Antwort akzeptieren :). Vielleicht können Sie die neue Frage auch separat stellen?
Suresh Venkat
erledigt. Die neue Frage ist jetzt in cstheory.stackexchange.com/questions/3614/…
Marcos Villagra
Kurz bevor ich es akzeptiere, möchte ich abwarten, ob jemand eine andere Untergrenze kennt, z. B. eine informationstheoretische Grenze
Marcos Villagra