Document Open Access Logo

Small Circuits Imply Efficient Arthur-Merlin Protocols

Authors Michael Ezra, Ron D. Rothblum

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.67.pdf
  • Filesize: 0.75 MB
  • 16 pages

Document Identifiers

Author Details

Michael Ezra
  • Department of Computer Science, Technion, Haifa, Israel
Ron D. Rothblum
  • Department of Computer Science, Technion, Haifa, Israel

Acknowledgements

We thank Yuval Ishai, Eyal Kushilevitz and Or Meir for very useful discussions and comments.

Cite As Get BibTex

Michael Ezra and Ron D. Rothblum. Small Circuits Imply Efficient Arthur-Merlin Protocols. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.67

Abstract

The inner product function ⟨ x,y ⟩ = ∑_i x_i y_i mod 2 can be easily computed by a (linear-size) AC⁰(⊕) circuit: that is, a constant depth circuit with AND, OR and parity (XOR) gates. But what if we impose the restriction that the parity gates can only be on the bottom most layer (closest to the input)? Namely, can the inner product function be computed by an AC⁰ circuit composed with a single layer of parity gates? This seemingly simple question is an important open question at the frontier of circuit lower bound research.

In this work, we focus on a minimalistic version of the above question. Namely, whether the inner product function cannot be approximated by a small DNF augmented with a single layer of parity gates. Our main result shows that the existence of such a circuit would have unexpected implications for interactive proofs, or more specifically, for interactive variants of the Data Streaming and Communication Complexity models. In particular, we show that the existence of such a small (i.e., polynomial-size) circuit yields:

1) An O(d)-message protocol in the Arthur-Merlin Data Streaming model for every n-variate, degree d polynomial (over GF(2)), using only Õ(d) ⋅log(n) communication and space complexity. In particular, this gives an AM[2] Data Streaming protocol for a variant of the well-studied triangle counting problem, with poly-logarithmic communication and space complexities.

2) A 2-message communication complexity protocol for any sparse (or low degree) polynomial, and for any function computable by an AC⁰(⊕) circuit. Specifically, for the latter, we obtain a protocol with communication complexity that is poly-logarithmic in the size of the AC⁰(⊕) circuit.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Circuits Complexity
  • Circuit Lower Bounds
  • Communication Complexity
  • Data Streaming
  • Arthur-Merlin games
  • Interactive Proofs

Metrics

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

Related Versions

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1-2:54, 2009. URL: https://doi.org/10.1145/1490270.1490272.
  2. Miklós Ajtai. ∑^1_1-formulae on finite structures. Ann. Pure Appl. Log., 24(1):1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
  3. Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC⁰∘mod₂. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 251-260. ACM, 2014. URL: https://doi.org/10.1145/2554797.2554821.
  4. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. URL: https://doi.org/10.1006/jcss.1997.1545.
  5. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking Computations in Polylogarithmic Time. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21-31. ACM, 1991. URL: https://doi.org/10.1145/103418.103428.
  6. László Babai and Shlomo Moran. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci., 36(2):254-276, 1988. URL: https://doi.org/10.1016/0022-0000(88)90028-1.
  7. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In David Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 623-632. ACM/SIAM, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545464.
  8. Suman K. Bera and Amit Chakrabarti. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 11:1-11:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.11.
  9. Mark Bun, Robin Kothari, and Justin Thaler. Quantum algorithms and approximating polynomials for composed functions with shared inputs, 2020. URL: http://arxiv.org/abs/1809.02254.
  10. Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Stijn Vansummeren, editor, Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA, pages 253-262. ACM, 2006. URL: https://doi.org/10.1145/1142351.1142388.
  11. Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler. Annotations for sparse data streams. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 687-706. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.52.
  12. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in data streams. ACM Trans. Algorithms, 11(1):7:1-7:30, 2014. URL: https://doi.org/10.1145/2636924.
  13. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. On interactivity in Arthur-Merlin communication and stream computation. Electron. Colloquium Comput. Complex., 20:180, 2013. URL: http://eccc.hpi-web.de/report/2013/180.
  14. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable Stream Computation and Arthur-Merlin communication. In David Zuckerman, editor, 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, volume 33 of LIPIcs, pages 217-243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.217.
  15. Amit Chakrabarti, Prantar Ghosh, and Justin Thaler. Streaming verification for graph problems: Optimal tradeoffs and nonlinear sketches. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 22:1-22:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.22.
  16. Lijie Chen, Xin Lyu, and R. Ryan Williams. Almost-everywhere circuit lower bounds from non-trivial derandomization. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1-12. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00009.
  17. Lijie Chen and Hanlin Ren. Strong average-case lower bounds from non-trivial derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1327-1334. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384279.
  18. Lijie Chen and R. Ryan Williams. Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 19:1-19:43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.19.
  19. Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC⁰∘mod₂ lower bounds for the boolean inner product. J. Comput. Syst. Sci., 97:45-59, 2018. URL: https://doi.org/10.1016/j.jcss.2018.04.006.
  20. Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 47-58. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840734.
  21. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. Proc. VLDB Endow., 5(1):25-36, 2011. URL: https://doi.org/10.14778/2047485.2047488.
  22. Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler. Limits of Preprocessing. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 17:1-17:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.17.
  23. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981, pages 260-270. IEEE Computer Society, 1981. URL: https://doi.org/10.1109/SFCS.1981.35.
  24. Dmitry Gavinsky and Alexander A. Sherstov. A separation of NP and conp in multiparty communication complexity. Theory Comput., 6(1):227-245, 2010. URL: https://doi.org/10.4086/toc.2010.v006a010.
  25. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 86:1-86:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.86.
  26. Parikshit Gopalan, Adam R. Klivans, and David Zuckerman. List-decoding Reed-Muller codes over small fields. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 265-274. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374417.
  27. Tom Gur and Ran Raz. Arthur-Merlin streaming complexity. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 528-539. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_45.
  28. Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 39:1-39:43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.39.
  29. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20. ACM, 1986. URL: https://doi.org/10.1145/12130.12132.
  30. Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine extractors and AC0-Parity. Electron. Colloquium Comput. Complex., page 137, 2021. URL: https://eccc.weizmann.ac.il/report/2021/137.
  31. Jeffrey C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. Syst. Sci., 55(3):414-440, 1997. URL: https://doi.org/10.1006/jcss.1997.1533.
  32. Madhav Jha, C. Seshadhri, and Ali Pinar. A space efficient streaming algorithm for triangle counting using the birthday paradox. In Inderjit S. Dhillon, Yehuda Koren, Rayid Ghani, Ted E. Senator, Paul Bradley, Rajesh Parekh, Jingrui He, Robert L. Grossman, and Ramasamy Uthurusamy, editors, The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11-14, 2013, pages 589-597. ACM, 2013. URL: https://doi.org/10.1145/2487575.2487678.
  33. Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 710-716. Springer, 2005. URL: https://doi.org/10.1007/11533719_72.
  34. Stasys Jukna. On graph complexity. Comb. Probab. Comput., 15(6):855-876, 2006. URL: https://doi.org/10.1017/S0963548306007620.
  35. John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 119-133. ACM, 2019. URL: https://doi.org/10.1145/3294052.3319706.
  36. Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, volume 7392 of Lecture Notes in Computer Science, pages 598-609. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_53.
  37. Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 118-134. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/CCC.2003.1214415.
  38. Hartmut Klauck. On arthur merlin games in communication complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 189-199. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/CCC.2011.33.
  39. Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis. Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Math., 8(1-2):161-185, 2012. URL: https://doi.org/10.1080/15427951.2012.625260.
  40. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, 1992. URL: https://doi.org/10.1145/146585.146605.
  41. Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 401-411. ACM, 2016. URL: https://doi.org/10.1145/2902251.2902283.
  42. Cody D. Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM J. Comput., 49(5), 2020. URL: https://doi.org/10.1137/18M1195887.
  43. Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett., 39(2):67-71, 1991. URL: https://doi.org/10.1016/0020-0190(91)90157-D.
  44. Alexander A Razborov. Lower bounds for the size of circuits of bounded depth with basis ∧, ⊕. Math. notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  45. Guy N. Rothblum. How to compute under AC⁰ leakage without secure hardware. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 552-569. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_32.
  46. Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 793-802. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488709.
  47. Ron D. Rothblum and Michael Ezra. Small Circuits Imply Efficient Arthur-Merlin Protocols. Electron. Colloquium Comput. Complex., page 127, 2021. URL: https://eccc.weizmann.ac.il/report/2021/127.
  48. Rocco A. Servedio and Emanuele Viola. On a special case of rigidity. Electron. Colloquium Comput. Complex., 19:144, 2012. URL: http://eccc.hpi-web.de/report/2012/144.
  49. Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172-216, 2005. URL: https://doi.org/10.1145/1059513.1059516.
  50. Ronen Shaltiel and Christopher Umans. Pseudorandomness for approximate counting and sampling. Comput. Complex., 15(4):298-341, 2006. URL: https://doi.org/10.1007/s00037-007-0218-9.
  51. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77-82. ACM, 1987. URL: https://doi.org/10.1145/28395.28404.
  52. Justin Thaler. Semi-streaming algorithms for annotated graph streams. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 59:1-59:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.59.
  53. Nikhil Vyas and R. Ryan Williams. Lower bounds against sparse symmetric functions of ACC circuits: Expanding the reach of #SAT algorithms. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 59:1-59:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.59.
  54. Ryan Williams. Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1-2:32, 2014. URL: https://doi.org/10.1145/2559903.
  55. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209-213. ACM, 1979. URL: https://doi.org/10.1145/800135.804414.
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