Document Open Access Logo

Hardness of Constant-Round Communication Complexity

Authors Shuichi Hirahara, Rahul Ilango, Bruno Loff

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2021.31.pdf
  • Filesize: 0.86 MB
  • 30 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Problems, reductions and completeness
Keywords
  • NP-completeness
  • Communication Complexity
  • Round Elimination Lemma
  • Meta-Complexity

Metrics

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

Abstract

How difficult is it to compute the communication complexity of a two-argument total Boolean function f:[N]×[N] → {0,1}, when it is given as an N×N binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard. 
In this work, we show that it is NP-hard to approximate the size (number of leaves) of the smallest constant-round protocol for a two-argument total Boolean function f:[N]×[N] → {0,1}, when it is given as an N×N binary matrix. Along the way to proving this, we show a new deterministic variant of the round elimination lemma, which may be of independent interest.

Cite As Get BibTex

Shuichi Hirahara, Rahul Ilango, and Bruno Loff. Hardness of Constant-Round Communication Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 31:1-31:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.31

Author Details

Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan
Rahul Ilango
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Bruno Loff
  • INESC-Tec and University of Porto, Portugal

Funding

  • Hirahara, Shuichi: This work was partly carried out during a visit supported by ACT-I, JST.
  • Ilango, Rahul: During this work, this author was funded by an Akamai Presidential Fellowship and by NSF Grants CCF-1741615 and CCF-1909429.
  • Loff, Bruno: This project was financed by the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project UIDB/50014/2020. This work was partly carried out during a research visit conducted with support from DIMACS in association with its Special Focus on Lower Bounds.

Acknowledgements

The authors would like to thank Ryan Williams for his support, and for several discussions and suggestions, without which this paper would not have existed. The authors would also like to thank Igor Oliveira for helpful conversations about hardness of communication complexity.

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1):2, 2009. Google Scholar
  2. Miklós Ajtai. Σ¹₁-formulae on finite structures. Annals of pure and applied logic, 24(1):1-48, 1983. Google Scholar
  3. Miklós Ajtai and Michael Ben-Or. A Theorem on Probabilistic Constant Depth Computations. In Proceedings of the Symposium on Theory of Computing (STOC), pages 471-474, 1984. Google Scholar
  4. Eric Allender. The new complexity landscape around circuit minimization. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications (LATA), volume 12038 of Lecture Notes in Computer Science, pages 3-16. Springer, 2020. Google Scholar
  5. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 25-32, 2014. Google Scholar
  6. Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum circuit size, graph isomorphism, and related problems. SIAM Journal on Computing, 47(4):1339-1372, 2018. Google Scholar
  7. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing disjunctive normal form formulas and AC⁰ circuits given a truth table. SIAM Journal on Computing, 38(1):63-84, 2008. Google Scholar
  8. Eric Allender and Shuichi Hirahara. New insights on the (non-)hardness of circuit minimization and related problems. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  9. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. Computational Complexity, 26(2):469-496, 2017. Google Scholar
  10. Eric Allender, Rahul Ilango, and Neekon Vafa. The non-hardness of approximating circuit size. In International Computer Science Symposium in Russia (CSR), pages 13-24, 2019. Google Scholar
  11. Eric Allender and Michal Koucky. Amplifying lower bounds by means of self-reducibility. Journal of the ACM, 57(3):1-36, 2010. Google Scholar
  12. Eric Allender, Michal Koucky, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences, 77(1):14-40, 2011. Google Scholar
  13. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016. Google Scholar
  14. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the p=?np question. SIAM Journal on computing, 4(4):431-442, 1975. Google Scholar
  15. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM Journal on Computing, 42(3):1327-1363, 2013. Google Scholar
  16. Avrim L. Blum and Ronald L. Rivest. Training a 3-node neural network is np-complete. Neural Networks, 5(1):117-127, 1992. Google Scholar
  17. Joan Boyar, Philip Matthews, and René Peralta. On the shortest linear straight-line program for computing linear forms. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 168-179, 2008. Google Scholar
  18. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Conference on Computational Complexity (CCC), pages 10:1-10:24, 2016. Google Scholar
  19. Sebastian Lukas Arne Czort. The complexity of minimizing disjunctive normal form formulas. Master’s thesis, University of Aarhus, 1999. Google Scholar
  20. Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, 1998. Google Scholar
  21. Vitaly Feldman. Hardness of approximate two-level logic minimization and PAC learning with membership queries. In Symposium on Theory of Computing (STOC), pages 363-372, 2006. Google Scholar
  22. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. ac⁰[p] lower bounds against mcsp via the coin problem. In Colloquium on Automata, Languages, and Programming (ICALP), volume 132, page 66, 2019. Google Scholar
  23. Thomas R. Hancock, Tao Jiang, Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Information and Computation, 126(2):114-122, 1996. Google Scholar
  24. Johan Hastad. Clique is hard to approximate within n^1-ε. In Symposium on Foundations of Computer Science (FOCS), pages 627-636, 1996. Google Scholar
  25. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In Computational Complexity Conference (CCC), pages 5:1-5:31, 2018. Google Scholar
  26. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. Google Scholar
  27. John M. Hitchcock and Aduri Pavan. On the NP-completeness of the minimum circuit size problem. In Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. Google Scholar
  28. Rahul Ilango. Approaching MCSP from above and below: Hardness for a conditional variant and ac⁰[p]. In Thomas Vidick, editor, Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of LIPIcs, pages 34:1-34:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  29. Rahul Ilango. Constant depth formula and partial function versions of MCSP are hard. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 424-433. IEEE, 2020. Google Scholar
  30. Rahul Ilango, Bruno Loff, and Igor Carboni Oliveira. Np-hardness of circuit minimization for multi-output functions. In Shubhangi Saraf, editor, Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 22:1-22:36. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  31. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The Power of Natural Properties as Oracles. In Computational Complexity Conference (CCC), volume 102, pages 7:1-7:20, 2018. Google Scholar
  32. J. Stephen Judd. Learning in networks is hard. In International Conference on Neural Networks (ICNN), volume 2, pages 685-692, 1987. Google Scholar
  33. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  34. Mauricio Karchmer, Eyal Kushilevitz, and Noam Nisan. Fractional covers and communication complexity. SIAM Journal on Discrete Mathematics, 8(1):76-92, 1995. Google Scholar
  35. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, page 539–550. Association for Computing Machinery, 1988. Google Scholar
  36. Subhash Khot and Rishi Saket. Hardness of minimizing and learning DNF expressions. In Symposium on Foundations of Computer Science (FOCS), pages 231-240, 2008. Google Scholar
  37. Jan Krajícek. Forcing with Random Variables and Proof Complexity. Cambridge University Press, 2011. Google Scholar
  38. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  39. Eyal Kushilevitz and Enav Weinreb. On the complexity of communication complexity. In Symposium on Theory of Computing (STOC), pages 465-474, 2009. Google Scholar
  40. Yanyi Liu and Rafael Pass. On one-way functions and kolmogorov complexity. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.11514.
  41. L. Lovasz and M. Saks. Lattices, mobius functions and communications complexity. In Symposium on Foundations of Computer Science (FOCS), SFCS '88, page 81–90, USA, 1988. IEEE Computer Society. Google Scholar
  42. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960-981, 1994. Google Scholar
  43. William J. Masek. Some NP-complete set covering problems. Unpublished Manuscript, 1979. Google Scholar
  44. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Symposium on Theory of Computing (STOC), STOC 2019, page 1215–1225, New York, NY, USA, 2019. Association for Computing Machinery. Google Scholar
  45. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Symposium on Theory of Computing (STOC), 2019. Google Scholar
  46. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1):37-49, 1998. Google Scholar
  47. Moritz Müller and Ján Pich. Feasibly constructive proofs of succinct weak circuit lower bounds. Annals of Pure and Applied Logic, 171(2), 2020. Google Scholar
  48. Cody D. Murray and Richard Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In Conference on Computational Complexity (CCC), pages 365-380, 2015. Google Scholar
  49. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM journal on computing, 22(4):838-856, 1993. Google Scholar
  50. Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM, 51(2):231-262, 2004. Google Scholar
  51. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and Near-Optimal Derandomization. In Symposium on Foundations of Computer Science (FOCS), pages 182-191, 1995. Google Scholar
  52. Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63-70, 1991. Google Scholar
  53. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In Conference on Computational Complexity (CCC), 2019. Google Scholar
  54. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. Google Scholar
  55. Igor Carboni Oliveira and Rahul Santhanam. Hardness magnification for natural problems. In Symposium on Foundations of Computer Science (FOCS), pages 65-76, 2018. Google Scholar
  56. Denis Pankratov. Direct sum questions in classical communication complexity. Master’s thesis, University of Chicago, 2012. Google Scholar
  57. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35(4):965-984, 1988. Google Scholar
  58. Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. Google Scholar
  59. Alexander A Razborov. On submodular complexity measures. Boolean Function Complexity,(M. Paterson, Ed.), pages 76-83, 1992. Google Scholar
  60. Alexander A Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  61. Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  62. Pranab Sen and Srinivasan Venkatesh. Lower bounds for predecessor searching in the cell probe model. Journal of Computer and System Sciences, 74(3):364-385, 2008. Google Scholar
  63. Boris A Trakhtenbrot. A survey of Russian approaches to perebor (brute-force search) algorithms. Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  64. Christopher Umans, Tiziano Villa, and Alberto L. Sangiovanni-Vincentelli. Complexity of two-level logic minimization. IEEE Transactions on CAD of Integrated Circuits and Systems, 25(7):1230-1246, 2006. Google Scholar
  65. David Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-128, 2007. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact