Improved Separations between Nondeterministic and Randomized Multiparty Communication
ACM Transactions on Computation Theory · 2009
DOI: 10.1145/1595391.1595392 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2009. Verfasst von Matei David und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 32 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations.
Abstract (Originalsprache)
We exhibit an explicit function f : {0, 1} n →{0, 1} that can be computed by a nondeterministic number-on-forehead protocol communicating O (log n ) bits, but that requires n Ω(1) bits of communication for randomized number-on-forehead protocols with k = δ ·log n players, for any fixed δ < 1. Recent breakthrough results for the Set-Disjointness function [Lee and Shraibman 2008; Chattopadhyay and Ada 2008] based on the work of Sherstov [2009; 2008a] imply such a separation but only when the number of players is k < loglog n . We also show that for any k = A ·loglog n the above function f is computable by a small circuit whose depth is constant whenever A is a (possibly large) constant. Recent results again give such functions but only when the number of players is k < loglog n .
Förderung
- Division of Computing and Communication Foundations
Zitieren
APA
David, M., Pitassi, T., & Viola, E. (2009). Improved Separations between Nondeterministic and Randomized Multiparty Communication. ACM Transactions on Computation Theory. https://doi.org/10.1145/1595391.1595392
Vancouver
David M, Pitassi T, Viola E. Improved Separations between Nondeterministic and Randomized Multiparty Communication. ACM Transactions on Computation Theory. 2009. doi:10.1145/1595391.1595392
BibTeX
@article{David2009,
author = {David, Matei and Pitassi, Toniann and Viola, Emanuele},
title = {Improved Separations between Nondeterministic and Randomized Multiparty Communication},
journal = {ACM Transactions on Computation Theory},
year = {2009},
doi = {10.1145/1595391.1595392}
}
EUVIMED