Document Open Access Logo

The Power of Super-logarithmic Number of Players

Authors Arkadev Chattopadhyay, Michael E. Saks

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.596.pdf
  • Filesize: 433 kB
  • 8 pages

Document Identifiers

Author Details

Arkadev Chattopadhyay
Michael E. Saks

Cite As Get BibTex

Arkadev Chattopadhyay and Michael E. Saks. The Power of Super-logarithmic Number of Players. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 596-603, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.596

Abstract

In the `Number-on-Forehead' (NOF) model of multiparty communication,
 the input is a k times m boolean matrix A (where k is the number of players) and Player i sees all bits except those in the i-th row, and the players communicate by broadcast in order to evaluate a specified function f at A.

We discover new computational power when k exceeds log m. We give a protocol with communication cost poly-logarithmic in m, for block composed functions with limited block width.  These are functions 
of the form f o g where f is a symmetric b-variate function, and g is a (kr)-variate function and (f o g)(A) is defined, for a k times (br) matrix to be f(g(A-1),...,g(A-b)) where A-i is the i-th (k times r) block of A. Our protocol works provided that k > 1+ ln b + (2 to the power of r).  

Ada et al. (ICALP'2012) previously obtained simultaneous and deterministic efficient protocols for composed functions of block-width one. The new protocol is the first to work for block composed functions with block-width greather than one. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

Subject Classification

Keywords
  • Communication complexity
  • Number-On-Forehead model
  • composed functions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Ada. Communication complexity. PhD thesis, McGill University, 2013. Google Scholar
  2. A. Ada, A. Chattopadhyay, O. Fawzi, and P. Nguyen. The NOF multiparty communication complexity of composed functions. In International Colloquium on Automata, Languages and Programming (ICALP), pages 13-24, 2012. Google Scholar
  3. L. Babai, A. Gál, P. G. Kimmel, and S. V. Lokam. Communication complexity of simultaneous messages. SIAM J. of Computing, 33:137-166, 2003. Google Scholar
  4. L. Babai, P. G. Kimmel, and S. V. Lokam. Simultaneous messages vs. communication. In 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 361-372. Springer, 1995. Google Scholar
  5. L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. Journal of Computer and System Sciences, 45(2):204-232, 1992. Google Scholar
  6. P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Computational Complexity, 15(4):391-432, 2006. Google Scholar
  7. Richard Beigel and Jun Tarui. On ACC. Computational Complexity, 4:350-366, 1994. Google Scholar
  8. A. K. Chandra, M. L. Furst, and R. J. Lipton. Multiparty protocols. In 15th ACM Symposium on Theory of Computing (STOC), pages 94-99, 1983. Google Scholar
  9. A. Chattopadhyay and A. Ada. Multiparty communication complexity of disjointness. Technical Report TR08-002, Electronic Colloquium on Computational Complexity (ECCC), 2008. Google Scholar
  10. A. Chattopadhyay, A. Krebs, M. Koucký, M. Szegedy, P. Tesson, and D. Thérien. Languages with bounded multiparty communication complexity. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 500-511, 2007. Google Scholar
  11. M. David, T. Pitassi, and E. Viola. Improved separations between nondeterministic and randomized multiparty communication. ACM Transactions on Computation Theory (TOCT), 1(2), 2009. Google Scholar
  12. V. Grolmusz. The BNS lower bound for multi-party protocols is nearly optimal. Information and Computation, 112:51-54, 1994. Google Scholar
  13. Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1:113-129, 1991. Google Scholar
  14. T. Lee and A. Shraibman. Disjointness is hard in the multiparty number-on-the-forehead model. Computational Complexity, 18(2):309-336, 2009. Google Scholar
  15. A. A. Razborov. Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Math. Notes of the Acad. of Sci. of USSR, 41(3):333-338, 1987. Google Scholar
  16. A. A. Sherstov. The multiparty communication complexity of set disjointness. In 44th Symposium on Theory of Computing (STOC), 2012. Google Scholar
  17. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In 19th Annual ACM Symposium on Theory of Computing, pages 77-82. ACM Press, 1987. Google Scholar
  18. E. Viola and A. Wigderson. Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(1):137-168, 2008. Google Scholar
  19. Ryan Williams. Non-uniform ACC circuit lower bounds. In IEEE Conference on Computational Complexity, pages 115-125, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact