Document Open Access Logo

A Hierarchy Theorem for Interactive Proofs of Proximity

Authors Tom Gur, Ron D. Rothblum

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.39.pdf
  • Filesize: 0.98 MB
  • 43 pages

Document Identifiers

Author Details

Tom Gur
Ron D. Rothblum

Cite As Get BibTex

Tom Gur and Ron D. Rothblum. A Hierarchy Theorem for Interactive Proofs of Proximity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 39:1-39:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.39

Abstract

The number of rounds, or round complexity, used in an interactive
protocol is a fundamental resource. In this work we consider the
significance of round complexity in the context of Interactive
Proofs of Proximity (IPPs). Roughly speaking, IPPs are interactive proofs in which the verifier runs in sublinear time and is only required to reject inputs that are far from the language.

Our main result is a round hierarchy theorem for IPPs, showing
that the power of IPPs grows with the number of rounds. More
specifically, we show that there exists a gap function
g(r) = Theta(r^2) such that for every constant r \geq 1 there exists a language that (1) has a g(r)-round IPP with   verification time t=t(n,r) but (2) does not have an r-round  IPP with verification time t (or even verification time  t'=\poly(t)).

In fact, we prove a stronger result by exhibiting a single language L such that, for every constant r \geq 1, there is an
O(r^2)-round IPP for L with t=n^{O(1/r)} verification time, whereas the verifier in any r-round IPP for L must run in time at least t^{100}. Moreover, we show an IPP for L with a poly-logarithmic number of rounds and only poly-logarithmic erification time, yielding a sub-exponential separation between the power of constant-round IPPs versus general (unbounded round) IPPs.

From our hierarchy theorem we also derive implications to standard
interactive proofs (in which the verifier can run in polynomial
time). Specifically, we show that the round reduction technique of
Babai and Moran (JCSS, 1988) is (almost) optimal among all blackbox transformations, and we show a connection to the algebrization framework of Aaronson and Wigderson (TOCT, 2009).

Subject Classification

Keywords
  • Complexity Theory
  • Property Testing
  • Interactive Proofs

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. ACM Trans. Comput. Theory, 1:2:1-2:54, February 2009. URL: http://dx.doi.org/10.1145/1490270.1490272.
  2. William Aiello, Shafi Goldwasser, and Johan Håstad. On the power of interaction. Combinatorica, 10(1):3-25, 1990. URL: http://dx.doi.org/10.1007/BF02122692.
  3. Miklós Ajtai, János Komlós, and Endre Szemerédi. An O(n log n) sorting network. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 1-9, 1983. URL: http://dx.doi.org/10.1145/800061.808726.
  4. Sanjeev Arora and Madhu Sudan. Improved low-degree testing and its applications. Combinatorica, 23(3):365-426, 2003. URL: http://dx.doi.org/10.1007/s00493-003-0025-0.
  5. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In STOC, pages 21-31, 1991. URL: http://dx.doi.org/10.1145/103418.103428.
  6. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991. URL: http://dx.doi.org/10.1007/BF01200056.
  7. Laszlo Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 337-347, Washington, DC, USA, 1986. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFCS.1986.15.
  8. László Babai and Shlomo Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36(2):254-276, 1988. Google Scholar
  9. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM Journal on computing, 4(4):431-442, 1975. Google Scholar
  10. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 261-270, 2016. URL: http://dx.doi.org/10.1145/2840728.2840746.
  11. Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler. Annotations for sparse data streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 687-706. SIAM, 2014. Google Scholar
  12. Amit Chakrabarti, Graham Cormode, and Andrew Mcgregor. Annotations in data streams. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP '09, pages 222-234, Berlin, Heidelberg, 2009. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-02927-1_20.
  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), volume 33, pages 217-243. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  14. Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39, 1994. Google Scholar
  15. Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, and Ron D. Rothblum. Efficient multiparty protocols via log-depth threshold formulae - (extended abstract). In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II, pages 185-202, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40084-1_11.
  16. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 90-112. ACM, 2012. Google Scholar
  17. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming graph computations with a helpful advisor. Algorithmica, 65(2):409-442, 2013. Google Scholar
  18. Samira Daruki, Justin Thaler, and Suresh Venkatasubramanian. Streaming verification in data analysis. arXiv preprint arXiv:1509.05514, 2015. Google Scholar
  19. 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.
  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 Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 1163-1182. IEEE, 2015. Google Scholar
  22. Lance Fortnow and Michael Sipser. Are there interactive protocols for CO-NP languages? Inf. Process. Lett., 28(5):249-251, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90199-8.
  23. Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. Inf. Process. Lett., 43(4):169-174, 1992. URL: http://dx.doi.org/10.1016/0020-0190(92)90195-2.
  24. Oded Goldreich. Computational complexity - a conceptual perspective. Cambridge University Press, 2008. Google Scholar
  25. Oded Goldreich. Valiant’s polynomial-size monotone formula for majority. Unpublished, 2011. URL: http://www.wisdom.weizmann.ac.il/~oded/PDF/mono-maj.pdf.
  26. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html.
  27. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  28. 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.
  29. 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.
  30. 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.
  31. Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for context-free languages and read-once branching programs - (extended abstract). In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 666-677, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_54.
  32. Oded Goldreich, Yishay Mansour, and Michael Sipser. Interactive proof systems: Provers that never fail and random selection (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 449-461, 1987. URL: http://dx.doi.org/10.1109/SFCS.1987.35.
  33. Oded Goldreich and Dana Ron. On sample-based testers. Electronic Colloquium on Computational Complexity (ECCC), 20:109, 2013. URL: http://eccc.hpi-web.de/report/2013/109.
  34. Oded Goldreich and Dana Ron. On learning and testing dynamic environments. Electronic Colloquium on Computational Complexity (ECCC), 21:29, 2014. URL: http://eccc.hpi-web.de/report/2014/029/.
  35. Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. J. ACM, 53(4):558-655, 2006. URL: http://dx.doi.org/10.1145/1162349.1162351.
  36. Oded Goldreich, Salil P. Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1-2):1-53, 2002. URL: http://dx.doi.org/10.1007/s00037-002-0169-0.
  37. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In STOC, pages 113-122, 2008. Google Scholar
  38. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. URL: http://dx.doi.org/10.1137/0218012.
  39. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 59-68. ACM, 1986. Google Scholar
  40. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. Electronic Colloquium on Computational Complexity (ECCC), 22:49, 2015. URL: http://eccc.hpi-web.de/report/2015/049.
  41. 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.
  42. Tom Gur and Ran Raz. Arthur-Merlin streaming complexity. Information and Computation, 243:145-165, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.011.
  43. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Computational Complexity, pages 1-109, 2016. URL: http://dx.doi.org/10.1007/s00037-016-0136-9.
  44. Shlomo Hoory, Avner Magen, and Toniann Pitassi. Monotone circuits for the majority function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pages 410-425, 2006. URL: http://dx.doi.org/10.1007/11830924_38.
  45. Yael Kalai and Guy N. Rothblum. Constant-round interactive proofs for NC¹. Unpublished observation, 2009. Google Scholar
  46. Yael Tauman Kalai and Ran Raz. Interactive PCP. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, pages 536-547, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70583-3_44.
  47. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. Delegation for bounded space. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 565-574, 2013. URL: http://dx.doi.org/10.1145/2488608.2488679.
  48. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: the power of no-signaling proofs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 485-494, 2014. URL: http://dx.doi.org/10.1145/2591796.2591809.
  49. Yael Tauman Kalai and Ron D. Rothblum. Arguments of proximity - [extended abstract]. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 422-442, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48000-7_21.
  50. Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, pages 723-732, 1992. Google Scholar
  51. Hartmut Klauck. On Arthur Merlin games in communication complexity. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pages 189-199. IEEE, 2011. Google Scholar
  52. 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.
  53. Or Meir. IP = PSPACE using error-correcting codes. SIAM J. Comput., 42(1):380-403, 2013. URL: http://dx.doi.org/10.1137/110829660.
  54. Ran Raz, Gábor Tardos, Oleg Verbitsky, and Nikolai Vereshagin. Arthur-Merlin games in boolean decision trees. In Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on, pages 58-67. IEEE, 1998. Google Scholar
  55. A. Razborov. Lower bounds for the size of circuits of bounded depth with basis ∧, ⊕. Notes of the Academy of Science of the USSR: 41(4) : 333-338, 1987. Google Scholar
  56. 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.
  57. Guy N. Rothblum. Delegating computation reliably: paradigms and constructions. PhD thesis, Massachusetts Institute of Technology, 2009. Google Scholar
  58. Guy N. Rothblum, Salil Vadhan, and Avi Wigderson. Interactive proofs of proximity: Delegating computation in sublinear time. In Proceedings of the 45th annual ACM Symposium on Theory of Computing (STOC), 2013. Google Scholar
  59. 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.
  60. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. Google Scholar
  61. Alexander A Sherstov. The multiparty communication complexity of set disjointness. In Proceedings of the 44th symposium on Theory of Computing, pages 525-548. ACM, 2012. Google Scholar
  62. R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, STOC '87, pages 77-82, New York, NY, USA, 1987. ACM. URL: http://dx.doi.org/10.1145/28395.28404.
  63. Madhu Sudan. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. PhD thesis, University of California at Berkeley, Berkeley, CA, USA, 1992. UMI Order No. GAX93-30747. Google Scholar
  64. Madhu Sudan. Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems, volume 1001 of Lecture Notes in Computer Science. Springer, 1995. URL: http://dx.doi.org/10.1007/3-540-60615-7.
  65. 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 17:1-17:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.17.
  66. Salil P. Vadhan. On transformation of interactive proofs that preserve the prover’s complexity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 200-207, 2000. URL: http://dx.doi.org/10.1145/335305.335330.
  67. Leslie G. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5(3):363-366, 1984. URL: http://dx.doi.org/10.1016/0196-6774(84)90016-6.
  68. Emanuele Viola. Guest column: correlation bounds for polynomials over 0 1. SIGACT News, 40(1):27-44, 2009. URL: http://dx.doi.org/10.1145/1515698.1515709.
  69. Richard Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 2:1-2:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.2.
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