Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Improved Separations between Nondeterministic and Randomized Multiparty Communication

Improved Separations between Nondeterministic and Randomized Multiparty Communication 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 . http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Improved Separations between Nondeterministic and Randomized Multiparty Communication

Download PDF
20 pages

Loading next page...
 
/lp/association-for-computing-machinery/improved-separations-between-nondeterministic-and-randomized-HH5bo2rdLm
Publisher
Association for Computing Machinery
Copyright
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Subject
Relations among complexity measures
ISSN
1942-3454
DOI
10.1145/1595391.1595392
Publisher site
See Article on Publisher Site

Abstract

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 .

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Sep 1, 2009

There are no references for this article.