Document Open Access Logo

Efficient Interactive Proofs for Non-Deterministic Bounded Space

Authors Joshua Cook , Ron D. Rothblum

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2023.47.pdf
  • Filesize: 0.85 MB
  • 22 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive Proofs
  • Alternating Algorithms
  • AC0[2]
  • Doubly Efficient Proofs

Metrics

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

Abstract

The celebrated IP = PSPACE Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch’s Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols for nondeterministic algorithms directly to get faster verifiers.
More specifically, for any non-deterministic space S algorithm, we construct an interactive proof in which the verifier runs in time Õ(n+S²). This improves on the best previous bound of Õ(n+S³) and matches the result for deterministic space bounded algorithms, up to polylog(S) factors.
We further generalize to alternating bounded space algorithms. For any language L decided by a time T, space S algorithm that uses d alternations, we construct an interactive proof in which the verifier runs in time Õ(n + S log(T) + S d) and the prover runs in time 2^O(S). For d = O(log(T)), this matches the best known interactive proofs for deterministic algorithms, up to polylog(S) factors, and improves on the previous best verifier time for nondeterministic algorithms by a factor of log(T). We also improve the best prior verifier time for unbounded alternations by a factor of S.
Using known connections of bounded alternation algorithms to bounded depth circuits, we also obtain faster verifiers for bounded depth circuits with unbounded fan-in.

Cite As Get BibTex

Joshua Cook and Ron D. Rothblum. Efficient Interactive Proofs for Non-Deterministic Bounded Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.47

Author Details

Joshua Cook
  • Department of Computer Science, University of Texas Austin, TX, USA
Ron D. Rothblum
  • Faculty of Computer Science, Technion, Haifa, Israel

Funding

  • Cook, Joshua: Supported by the National Science Foundation under grant number 2200956.
  • Rothblum, Ron D.: Funded by the European Union (ERC, FASTPROOF, 101041208). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Acknowledgements

Thanks to Dana Moshkovitz for introducing the authors of this paper, and Anna Gál for finding the references relating low depth circuits to alternating algorithms.

References

  1. N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple construction of almost k-wise independent random variables. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 544-553 vol.2, 1990. URL: https://doi.org/10.1109/FSCS.1990.89575.
  2. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA, 1st edition, 2009. Google Scholar
  3. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, May 1998. URL: https://doi.org/10.1145/278298.278306.
  4. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. J. ACM, 45(1):70-122, January 1998. URL: https://doi.org/10.1145/273865.273901.
  5. L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 16-25 vol.1, 1990. URL: https://doi.org/10.1109/FSCS.1990.89520.
  6. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC '91, pages 21-32. Association for Computing Machinery, 1991. URL: https://doi.org/10.1145/103418.103428.
  7. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Theory of Cryptography Conference, 2016. Google Scholar
  8. Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. URL: https://doi.org/10.1145/322234.322243.
  9. Joshua Cook. More Verifier Efficient Interactive Protocols for Bounded Space. In Anuj Dawar and Venkatesan Guruswami, editors, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), volume 250 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2022.14.
  10. Joshua Cook. More verifier efficient interactive protocols for bounded space, 2022. URL: https://eccc.weizmann.ac.il/report/2022/093/.
  11. Joshua Cook and Ron Rothblum. Efficient interactive proofs for non-deterministic bounded space, 2023. URL: https://eccc.weizmann.ac.il/report/2023/097/.
  12. 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, ITCS '12, pages 90-112. Association for Computing Machinery, 2012. URL: https://doi.org/10.1145/2090236.2090245.
  13. Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, and Shmuel Safra. Pcp characterizations of np: Towards a polynomially-small error-probability. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC '99, pages 29-40. Association for Computing Machinery, 1999. URL: https://doi.org/10.1145/301250.301265.
  14. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Approximating clique is almost np-complete (preliminary version). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 2-12. IEEE Computer Society, 1991. URL: https://doi.org/10.1109/SFCS.1991.185341.
  15. Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC '92, pages 733-744. Association for Computing Machinery, 1992. URL: https://doi.org/10.1145/129712.129783.
  16. Lance Fortnow and Carsten Lund. Interactive proof systems and alternating time-space complexity. Theor. Comput. Sci., 113(1):55-73, 1993. URL: https://doi.org/10.1016/0304-3975(93)90210-K.
  17. Martin Fürer, Oded Goldreich, Y. Mansour, Michael Sipser, and Stathis Zachos. On completeness and soundness in interactive proof systems. Adv. Comput. Res., 5:429-442, 1989. Google Scholar
  18. Ofer Gabber and Zvi Galil. Explicit constructions of linear size superconcentrators. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 364-370, 1979. URL: https://doi.org/10.1109/SFCS.1979.16.
  19. Oded Goldreich. On doubly-efficient interactive proof systems, 2018. URL: https://www.wisdom.weizmann.ac.il/~oded/de-ip.html.
  20. Oded Goldreich and Guy N. Rothblum. Constant-Round Interactive Proof Systems for AC0[2] and NC1, pages 326-351. Springer International Publishing, Cham, 2020. URL: https://doi.org/10.1007/978-3-030-43662-9_18.
  21. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4), September 2015. URL: https://doi.org/10.1145/2699436.
  22. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. URL: https://doi.org/10.1137/0218012.
  23. Edward Hirsch, Dieter van Melkebeek, and Alexander Smal. Succinct interactive proofs for quantified boolean formulas, comment 2. Electronic Colloquium on Computational Complexity (ECCC), 2013. URL: https://eccc.weizmann.ac.il/report/2012/077/comment/2/download/.
  24. Nabil Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42(5):1091-1106, 1995. Google Scholar
  25. Yael Tauman Kalai and Ran Raz. Interactive pcp. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II, ICALP '08, pages 536-547. Springer-Verlag, 2008. URL: https://doi.org/10.1007/978-3-540-70583-3_44.
  26. C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 2-10 vol.1, 1990. URL: https://doi.org/10.1109/FSCS.1990.89518.
  27. Grigorii Aleksandrovich Margulis. Explicit construction of concentrators. Problemy Peredachi Informatsii, 9:325-332, 1973. URL: https://cir.nii.ac.jp/crid/1572824500389149056.
  28. Cody Murray and Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: An easy witness lemma for np and nqp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 890-901. Association for Computing Machinery, 2018. URL: https://doi.org/10.1145/3188745.3188910.
  29. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993. URL: https://doi.org/10.1137/0222053.
  30. Ran Raz. Quantum information and the pcp theorem. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, pages 459-468, USA, 2005. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.2005.62.
  31. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333-338, 1987. Google Scholar
  32. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 49-62. Association for Computing Machinery, 2016. URL: https://doi.org/10.1145/2897518.2897652.
  33. Rahul Santhanam. Circuit lower bounds for merlin-arthur classes. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 275-283. Association for Computing Machinery, 2007. URL: https://doi.org/10.1145/1250790.1250832.
  34. Adi Shamir. Ip = pspace. J. ACM, 39(4):869-877, October 1992. URL: https://doi.org/10.1145/146585.146609.
  35. A. Shen. Ip = space: Simplified proof. J. ACM, 39(4):878-880, 1992. URL: https://doi.org/10.1145/146585.146613.
  36. 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. Association for Computing Machinery, 1987. URL: https://doi.org/10.1145/28395.28404.
  37. Larry Stockmeyer and Uzi Vishkin. Simulation of parallel random access machines by circuits. SIAM Journal on Computing, 13(2):409-422, 1984. URL: https://doi.org/10.1137/0213027.
  38. Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 238-251. Association for Computing Machinery, 2017. URL: https://doi.org/10.1145/3055399.3055408.
  39. Justin Thaler. Time-optimal interactive proofs for circuit evaluation. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013, pages 71-89, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  40. Justin Thaler. The unreasonable power of the sum-check protocol, March 2020. URL: https://zkproof.org/2020/03/16/sum-checkprotocol/.
  41. Justin Thaler. Proofs, arguments, and zero-knowledge. Found. Trends Priv. Secur., 4(2-4):117-660, 2022. URL: https://doi.org/10.1561/3300000030.
  42. L. Trevisan and S. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. In Proceedings 17th IEEE Annual Conference on Computational Complexity, pages 129-138, 2002. URL: https://doi.org/10.1109/CCC.2002.1004348.
  43. Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1–3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  44. Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pages 733-764. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_24.
  45. Jiaheng Zhang, Tianyi Liu, Weijie Wang, Yinuo Zhang, Dawn Song, Xiang Xie, and Yupeng Zhang. Doubly efficient interactive proofs for general arithmetic circuits with linear prover time. In Yongdae Kim, Jong Kim, Giovanni Vigna, and Elaine Shi, editors, CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15-19, 2021, pages 159-177. ACM, 2021. URL: https://doi.org/10.1145/3460120.3484767.
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