Document Open Access Logo

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Authors Anup Rao, Amir Yehudayoff

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.88.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Anup Rao
Amir Yehudayoff

Cite AsGet BibTex

Anup Rao and Amir Yehudayoff. Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 88-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CCC.2015.88

Abstract

We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.
Keywords
  • communication complexity
  • set disjointness
  • number on forehead
  • lower bounds

Metrics

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

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. TOCT, 1(1), 2009. Google Scholar
  2. László Babai, Thomas P. Hayes, and Peter G. Kimmel. The cost of the missing bit: Communication complexity with help. Combinatorica, 21(4):455-488, 2001. Google Scholar
  3. László Babai, Noam Nisan, and Mario Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci., 45(2):204-232, 1992. Google Scholar
  4. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004. Google Scholar
  5. Paul Beame and Dang-Trinh Huynh-Ngoc. Multiparty communication complexity and threshold circuit size of AC⁰. In FOCS, pages 53-62, 2009. Google Scholar
  6. Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity. SIAM Journal on Computing, 37(3):845-869, 2007. Google Scholar
  7. Paul Beame, Toniann Pitassi, Nathan Segerlind, and Avi Wigderson. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Computational Complexity, 15(4):391-432, 2006. Google Scholar
  8. Mark Braverman and Ankur Moitra. An information complexity approach to extended formulations. In STOC, pages 161-170. ACM, 2013. Google Scholar
  9. Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In STOC, pages 94-99, 1983. Google Scholar
  10. Arkadev Chattopadhyay. Discrepancy and the power of bottom fan-in in depth-three circuits. In FOCS, pages 449-458. IEEE Computer Society Press, 2007. Google Scholar
  11. Arkadev Chattopadhyay. Circuits, Communication and Polynomials. PhD thesis, University of Toronto, 2008. Google Scholar
  12. Arkadev Chattopadhyay and Anil Ada. Multiparty communication complexity of disjointness. CoRR, abs/0801.3624, 2008. Google Scholar
  13. Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59-85, 2010. Google Scholar
  14. Elliot W. Cheney. Introduction to Approximation Theory. McGraw-Hill Book Co., New York, 1966. Google Scholar
  15. Fan R. K. Chung and Prasad Tetali. Communication complexity and quasi randomness. SIAM Journal on Discrete Mathematics, 6(1):110-123, February 1993. Google Scholar
  16. Vincent Conitzer and Tuomas Sandholm. Communication complexity as a lower bound for learning in games. In Carla E. Brodley, editor, ICML, volume 69 of ACM International Conference Proceeding Series. ACM, 2004. Google Scholar
  17. Shahar Dobzinski and Noam Nisan. Limitations of VCG-based mechanisms. Combinatorica, 31(4):379-396, 2011. Google Scholar
  18. H. Ehlich and K. Zeller. Schwankung von polynomen zwischen gitterpunkten. Mathematische Zeitschrift, 86:41-44, 1964. Google Scholar
  19. Vince Grolmusz. The bns lower bound for multi-party protocols in nearly optimal. Inf. Comput., 112(1):51-54, 1994. Google Scholar
  20. Sergiu Hart and Yishay Mansour. The communication complexity of uncoupled nash equilibrium procedures. In David S. Johnson and Uriel Feige, editors, STOC, pages 345-353. ACM, 2007. Google Scholar
  21. Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1:113-129, 1991. Google Scholar
  22. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, November 1992. Google Scholar
  23. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  24. Troy Lee and Adi Shraibman. Disjointness is hard in the multiparty number-on-the-forehead model. Computational Complexity, 18(2):309-336, 2009. Google Scholar
  25. Noam Nisan. The communication complexity of approximate set packing and covering. Lecture Notes in Computer Science, 2380:868-875, 2002. Google Scholar
  26. Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. J. Economic Theory, 129(1):192-224, 2006. Google Scholar
  27. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4(4):301-313, 1994. Google Scholar
  28. Noam Nisan and Avi Wigderson. Rounds in communication complexity revisited. SIAM Journal on Computing, 22(1):211-219, February 1993. Google Scholar
  29. Christos H. Papadimitriou, Michael Schapira, and Yaron Singer. On the hardness of being truthful. In FOCS, pages 250-259. IEEE Computer Society, 2008. Google Scholar
  30. Ran Raz. The BNS-chung criterion for multi-party communication complexity. Computational Complexity, 9(2):113-122, 2000. Google Scholar
  31. Alexander A. Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci., 106(2):385-390, 1992. Google Scholar
  32. Alexander A. Razborov and Avi Wigderson. n^ω(log n) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Information Processing Letters, 45(6):303-307, 1993. Google Scholar
  33. Theodore J. Rivlin and Elliott W. Cheney. A comparison of uniform approximations on an interval and a finite subset thereof. SIAM Journal on Numerical Analysis, 3(2):311-320, June 1966. Google Scholar
  34. Alexander A. Sherstov. Separating AC⁰ from depth-2 majority circuits. SIAM Journal of Computing, 38(6):2113-2129, 2009. Google Scholar
  35. Alexander A. Sherstov. The pattern matrix method. SIAM Journal of Computing, 40(6):1969-2000, 2011. Google Scholar
  36. Alexander A. Sherstov. The multiparty communication complexity of set disjointness. In STOC, pages 525-548, 2012. Google Scholar
  37. Alexander A. Sherstov. Communication lower bounds using directional derivatives. In STOC, pages 921-930, 2013. Google Scholar
  38. Pascal Tesson. Computational complexity questions related to finite monoids and semigroups. PhD thesis, McGill University, 2003. Google Scholar
  39. Emanuele Viola. Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM Journal on Computing, 36(5):1387-1403, 2007. Google Scholar
  40. Emanuele Viola and Avi Wigderson. Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(1):137-168, 2008. 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 Imprint Privacy Contact