Document Open Access Logo

Simultaneous Multiparty Communication Protocols for Composed Functions

Author Yassine Hamoudi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.14.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Yassine Hamoudi
  • IRIF, Université Paris Diderot, France

Cite As Get BibTex

Yassine Hamoudi. Simultaneous Multiparty Communication Protocols for Composed Functions. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.14

Abstract

The Number On the Forehead (NOF) model is a multiparty communication game between k players that collaboratively want to evaluate a given function F : X_1 x *s x X_k - > Y on some input (x_1,...,x_k) by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player i sees all of it except x_i (as if x_i is written on the forehead of player i). In the Simultaneous Message Passing (SMP) model, the players have the extra condition that they cannot speak to each other, but instead send information to a referee. The referee does not know the players' inputs, and cannot give any information back. At the end, the referee must be able to recover F(x_1,...,x_k) from what she obtained from the players.
A central open question in the simultaneous NOF model, called the log n barrier, is to find a function which is hard to compute when the number of players is polylog(n) or more (where the x_i's have size poly(n)). This has an important application in circuit complexity, as it could help to separate ACC^0 from other complexity classes [Håstad and Goldmann, 1991; Babai et al., 2004]. One of the candidates for breaking the log n barrier belongs to the family of composed functions. The input to these functions in the k-party NOF model is represented by a k x (t * n) boolean matrix M, whose row i is the number x_i on the forehead of player i and t is a block-width parameter. A symmetric composed function acting on M is specified by two symmetric n- and kt-variate functions f and g (respectively), that output f o g(M) = f(g(B_1),...,g(B_n)) where B_j is the j-th block of width t of M. As the majority function Maj is conjectured to be outside of ACC^0, Babai et. al. [Babai et al., 1995; Babai et al., 2004] suggested to study the composed function Maj o Maj_t, with t large enough, for breaking the log n barrier (where Maj_t outputs 1 if at least kt/2 bits of the input block are set to 1).
So far, it was only known that block-width t = 1 is not enough for Maj o Maj_t to break the log n barrier in the simultaneous NOF model [Babai et al., 2004] (Chattopadhyay and Saks [Chattopadhyay and Saks, 2014] found an efficient protocol for t <= polyloglog(n), but it requires randomness to be simultaneous). In this paper, we extend this result to any constant block-width t > 1 by giving a deterministic simultaneous protocol of cost 2^O(2^t) log^(2^(t+1))(n) for any symmetric composed function f o g (which includes Maj o Maj_t) when there are more than 2^Omega(2^t) log n players.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • Communication complexity
  • Number On the Forehead model
  • Simultaneous Message Passing
  • Log n barrier
  • Symmetric Composed functions

Metrics

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

References

  1. A. Ada, A. Chattopadhyay, O. Fawzi, and P. Nguyen. The NOF multiparty communication complexity of composed functions. Computational Complexity, 24(3):645-694, 2015. Google Scholar
  2. A. Ambainis. Communication complexity in a 3-computer model. Algorithmica, 16(3):298-301, 1996. Google Scholar
  3. L. Babai, A. Gál, P. G. Kimmel, and S. V. Lokam. Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137-166, 2004. Google Scholar
  4. L. Babai and P. G. Kimmel. Randomized simultaneous messages: solution of a problem of Yao in communication complexity. In Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, pages 239-246, 1997. Google Scholar
  5. 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
  6. L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci., 45(2):204-232, 1992. Google Scholar
  7. Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar. Information theory methods in communication complexity. In Proceedings 17th IEEE Annual Conference on Computational Complexity, pages 72-81, 2002. Google Scholar
  8. P. Beame and T. Huynh. Multiparty communication complexity and threshold circuit size of AC0. SIAM Journal on Computing, 41(3):484-518, 2012. Google Scholar
  9. P. Beame, T. Pitassi, and N. Segerlind. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput., 37(3):845-869, 2007. Google Scholar
  10. P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC '05, pages 52-66. IEEE Computer Society, 2005. Google Scholar
  11. P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Comput. Complex., 15(4):391-432, 2006. Google Scholar
  12. R. Beigel and J. Tarui. On ACC. Computational Complexity, 4(4):350-366, 1994. Google Scholar
  13. R. C. Bottesch, D. Gavinsky, and H. Klauck. Equality, revisited. CoRR, abs/1511.01211, 2015. Google Scholar
  14. H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87:167902, 2001. Google Scholar
  15. A. K. Chandra, M. L. Furst, and R. J. Lipton. Multi-party protocols. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, pages 94-99. ACM, 1983. Google Scholar
  16. A. Chattopadhyay and A. Ada. Multiparty communication complexity of disjointness. arXiv preprint arXiv:0801.3624, 2008. Google Scholar
  17. A. Chattopadhyay and M. E. Saks. The power of super-logarithmic number of players. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2014. Google Scholar
  18. F. R. K. Chung and P. Tetali. Communication complexity and quasi randomness. SIAMJDiscreteMath, 6(1):110-123, 1993. Google Scholar
  19. D. Gavinsky, O. Regev, and R. de Wolf. Simultaneous communication protocols with quantum and classical messages. Chicago Journal of Theoretical Computer Science, 7, 2008. Google Scholar
  20. T. Gowers and E. Viola. The communication complexity of interleaved group products. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pages 351-360. ACM, 2015. Google Scholar
  21. V. Grolmusz. The BNS lower bound for multi-party protocols is nearly optimal. Information and Computation, 112:51-54, 1994. Google Scholar
  22. J. Håstad and M. Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1(2):113-129, 1991. Google Scholar
  23. 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
  24. I. Newman and M. Szegedy. Public vs. private coin flips in one round communication games (extended abstract). In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 561-570. ACM, 1996. Google Scholar
  25. N. Nisan and A. Wigderson. Rounds in communication complexity revisited. SIAM J. Comput., 22(1):211-219, 1993. Google Scholar
  26. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  27. V. V. Podolskii and A. A. Sherstov. Inner product and set disjointness: Beyond logarithmically many parties. CoRR, abs/1711.10661, 2017. Google Scholar
  28. P. Pudlák, V. Rödl, and J. Sgall. Boolean circuits, tensor ranks, and communication complexity. SIAM J. Comput., 26(3):605-633, 1997. Google Scholar
  29. A. Rao and A. Yehudayoff. Simplified lower bounds on the multiparty communication complexity of disjointness. In Proceedings of the 30th Conference on Computational Complexity, CCC '15, pages 88-101, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  30. R. Raz. The BNS-Chung criterion for multi-party communication complexity. Computational Complexity, 9:2000, 2000. Google Scholar
  31. A. A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969-2000, 2011. Google Scholar
  32. A. A. Sherstov. Communication lower bounds using directional derivatives. J. ACM, 61(6):34:1-34:71, 2014. Google Scholar
  33. A. A. Sherstov. The multiparty communication complexity of set disjointness. SIAM Journal on Computing, 45(4):1450-1489, 2016. Google Scholar
  34. P. Tesson. Computational Complexity Questions Related to Finite Monoids and Semigroups. PhD thesis, McGill University, Montreal, Canada, 2003. Google Scholar
  35. R. Williams. Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1-2:32, 2014. Google Scholar
  36. A. Yao. Some complexity questions related to distributive computing. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209-213. ACM, 1979. Google Scholar
  37. A. Yao. On ACC and threshold circuits. In Proceedings 31st Annual Symposium on Foundations of Computer Science, pages 619-627 vol.2, 1990. 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