Document Open Access Logo

An Exponential Separation Between MA and AM Proofs of Proximity

Authors Tom Gur, Yang P. Liu, Ron D. Rothblum

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.73.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Tom Gur
  • UC Berkeley, Berkeley, USA
Yang P. Liu
  • MIT, Cambridge, MA
Ron D. Rothblum
  • MIT and Northeastern University, Cambridge, MA

Funding

  • Gur, Tom: Research supported in part by the UC Berkeley Center for Long-Term Cybersecurity.
  • Rothblum, Ron D.: Research supported in part by NSF Grants CNS-1350619 and CNS-1414119, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship and in part by the Defense Advanced Research Projects Agency (DARPA), the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236 and by the Cybersecurity and Privacy Institute at Northeastern University.

Cite As Get BibTex

Tom Gur, Yang P. Liu, and Ron D. Rothblum. An Exponential Separation Between MA and AM Proofs of Proximity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.73

Abstract

Interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work we consider two natural minimally interactive variants of such proofs systems, in which the prover only sends a single message, referred to as the proof.
The first variant, known as MA-proofs of Proximity (MAP), is fully non-interactive, meaning that the proof is a function of the input only. The second variant, known as AM-proofs of Proximity (AMP), allows the proof to additionally depend on the verifier's (entire) random string. The complexity of both MAPs and AMPs is the total number of bits that the verifier observes - namely, the sum of the proof length and query complexity.
Our main result is an exponential separation between the power of MAPs and AMPs. Specifically, we exhibit an explicit and natural property Pi that admits an AMP with complexity O(log n), whereas any MAP for Pi has complexity Omega~(n^{1/4}), where n denotes the length of the input in bits. Our MAP lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014).
Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier's queries are oblivious to the proof. In this setting we show that AMPs can only be quadratically stronger than MAPs. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive computation
Keywords
  • Property testing
  • Probabilistic proof systems
  • Proofs of proximity

Metrics

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

Related Versions

References

  1. Scott Aaronson. Impossibility of succinct quantum proofs for collision-freeness. Quantum Information & Computation, 12(1-2):21-28, 2012. URL: http://www.rintonpress.com/xxqic12/qic-12-12/0021-0028.pdf.
  2. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. TOCT, 1(1):2:1-2:54, 2009. URL: http://dx.doi.org/10.1145/1490270.1490272.
  3. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 25-36, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.12.
  4. Dorit Aharonov and Tomer Naveh. Quantum np-a survey. arXiv preprint quant-ph/0210077, 2002. Google Scholar
  5. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 337-347, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.15.
  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: http://dx.doi.org/10.1016/0022-0000(88)90028-1.
  7. Mihir Bellare and Moti Yung. Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology, 9(3):149-166, 1996. Google Scholar
  8. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust pcps of proximity, shorter pcps, and applications to coding. SIAM J. Comput., 36(4):889-974, 2006. URL: http://dx.doi.org/10.1137/S0097539705446810.
  9. Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-knowledge proofs of proximity. IACR Cryptology ePrint Archive, 2017:114, 2017. URL: http://eprint.iacr.org/2017/114.
  10. Mark Braverman. Poly-logarithmic independence fools bounded-depth boolean circuits. Commun. ACM, 54(4):108-115, 2011. URL: http://dx.doi.org/10.1145/1924421.1924446.
  11. Clément L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015. URL: http://eccc.hpi-web.de/report/2015/063.
  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: http://dx.doi.org/10.1145/2636924.
  13. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable stream computation and arthur-merlin communication. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 217-243, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.217.
  14. Alessandro Chiesa and Tom Gur. Proofs of proximity for distribution testing. ECCC, 24:155, 2017. URL: https://eccc.weizmann.ac.il/report/2017/155.
  15. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming graph computations with a helpful advisor. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, pages 231-242, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15775-2_20.
  16. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. PVLDB, 5(1):25-36, 2011. URL: http://www.vldb.org/pvldb/vol5/p025_grahamcormode_vldb2012.pdf.
  17. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36(4):975-1024, 2006. URL: http://dx.doi.org/10.1137/S0097539705446962.
  18. Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate probabilistically checkable proofs. Inf. Comput., 189(2):135-159, 2004. URL: http://dx.doi.org/10.1016/j.ic.2003.09.005.
  19. Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs under general assumptions. IAM J. Comput., 29(1), 1999. Preliminary version in FOCS'90. URL: http://dx.doi.org/10.1137/S0097539792230010.
  20. Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish. Partial tests, universal tests and decomposability. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 483-500, 2014. URL: http://dx.doi.org/10.1145/2554797.2554841.
  21. Eldar Fischer, Oded Lachish, and Yadu Vasudev. Trading query complexity for sample-based testing and multi-testing scalability. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1163-1182, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.75.
  22. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  23. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  24. Oded Goldreich and Tom Gur. Universal locally testable codes. Electronic Colloquium on Computational Complexity (ECCC), 23:42, 2016. URL: http://eccc.hpi-web.de/report/2016/042.
  25. Oded Goldreich and Tom Gur. Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Electronic Colloquium on Computational Complexity (ECCC), 23:192, 2016. URL: http://eccc.hpi-web.de/report/2016/192.
  26. Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong locally testable codes with relaxed local decoders. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 1-41, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.1.
  27. Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for context-free languages and read-once branching programs - (extended abstract). In International Colloquium on Automata, Languages and Programming ICALP, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_54.
  28. Oded Goldreich and Or Sheffet. On the randomness complexity of property testing. Computational Complexity, 19(1):99-133, 2010. URL: http://dx.doi.org/10.1007/s00037-009-0282-4.
  29. Mika Göös, Toniann Pitassi, and Thomas Watson. Zero-information protocols and unambiguity in arthur-merlin communication. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 113-122, 2015. URL: http://dx.doi.org/10.1145/2688073.2688074.
  30. Tom Gur. On Locally Verifiable Proofs of Proximity. PhD thesis, Weizmann Institute, 2017. Google Scholar
  31. Tom Gur, Yang P. Liu, and Ron D. Rothblum. An exponential separation between ma and am proofs of proximity, 2018. URL: https://eccc.weizmann.ac.il/report/2018/083/.
  32. Tom Gur and Ran Raz. Arthur-merlin streaming complexity. Inf. Comput., 243:145-165, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.011.
  33. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Computational Complexity, June 2016. Google Scholar
  34. Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In Innovations in Theoretical Computer Science ITCS, 2017. Google Scholar
  35. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Computational Complexity, 27(1):99-207, 2018. Google Scholar
  36. Yael Tauman Kalai and Ron D. Rothblum. Arguments of proximity - [extended abstract]. In CRYPTO, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48000-7_21.
  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, 2003. URL: http://dx.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, June 8-10, 2011, pages 189-199, 2011. URL: http://dx.doi.org/10.1109/CCC.2011.33.
  39. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, 1992. URL: http://dx.doi.org/10.1145/146585.146605.
  40. Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett., 39(2):67-71, 1991. URL: http://dx.doi.org/10.1016/0020-0190(91)90157-D.
  41. Ran Raz and Amir Shpilka. On the power of quantum proofs. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, pages 260-274, 2004. URL: http://dx.doi.org/10.1109/CCC.2004.1313849.
  42. Ran Raz, Gábor Tardos, Oleg Verbitsky, and Nikolai K. Vereshchagin. Arthur-merlin games in boolean decision trees. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998, pages 58-67, 1998. URL: http://dx.doi.org/10.1109/CCC.1998.694591.
  43. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 49-62, 2016. URL: http://dx.doi.org/10.1145/2897518.2897652.
  44. Dana Ron. Property testing: A learning theory perspective. Foundations and Trends in Machine Learning, 1(3):307-402, 2008. URL: http://dx.doi.org/10.1561/2200000004.
  45. Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5(2):73-205, 2009. URL: http://dx.doi.org/10.1561/0400000029.
  46. Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Symposium on Theory of Computing, STOC, 2013. URL: http://dx.doi.org/10.1145/2488608.2488709.
  47. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: http://dx.doi.org/10.1137/S0097539793255151.
  48. Alexander A. Sherstov. The multiparty communication complexity of set disjointness. SIAM J. Comput., 45(4):1450-1489, 2016. URL: http://dx.doi.org/10.1137/120891587.
  49. Justin Thaler. Semi-streaming algorithms for annotated graph streams. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 59:1-59:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.59.
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