Document Open Access Logo

More Verifier Efficient Interactive Protocols for Bounded Space

Author Joshua Cook

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.14.pdf
  • Filesize: 0.78 MB
  • 18 pages

Document Identifiers

Author Details

Joshua Cook
  • University of Texas at Austin, TX, USA

Funding

Funded by NSF grant number 1705028 and 2200956.

Acknowledgements

Thanks to Dana Moshkovitz for suggestions on writing and presentation, and Tayvin Otti for spellchecking.

Cite As Get BibTex

Joshua Cook. More Verifier Efficient Interactive Protocols for Bounded Space. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.14

Abstract

Let TISP[T, S], BPTISP[T, S], NTISP[T, S] and CoNTISP[T, S] be the set of languages recognized by deterministic, randomized, nondeterministic, and co-nondeterministic algorithms, respectively, running in time T and space S. Let ITIME[T_V, T_P] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V and the prover runs in time T_P.
For S = Ω(log(n)) and T constructible in time log(T) S + n, we prove:
TISP[T, S] ⊆ ITIME[Õ(log(T) S + n), 2^O(S)]
BPTISP[T, S] ⊆ ITIME[Õ(log(T) S + n), 2^O(S)]
NTISP[T, S] ⊆ ITIME[Õ(log(T)^2 S + n), 2^O(S)]
CoNTISP[T, S] ⊆ ITIME[Õ(log(T)^2 S + n), 2^O(S)] .
The best prior verifier time is from Shamir [Shamir, 1992; Lund et al., 1990]:  TISP[T, S] ⊆ ITIME[Õ(log(T)(S + n)), 2^O(log(T)(S + n))].
Our prover is faster, and our verifier is faster when S = o(n).
The best prior prover time uses ideas from Goldwasser, Kalai, and Rothblum [Goldwasser et al., 2015]:
NTISP[T, S] ⊆ ITIME[Õ(log(T) S² + n), 2^O(S)].
Our verifier is faster when log(T) = o(S), and for deterministic algorithms.
To our knowledge, no previous interactive protocol for TISP simultaneously has the same verifier time and prover time as ours. In our opinion, our protocol is also simpler than previous protocols.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive Proofs
  • Verifier Time
  • Randomized Space
  • Nondeterministic Space
  • Fine Grain Complexity

Metrics

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

Related Versions

References

  1. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA, 1st edition, 2009. Google Scholar
  2. 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, 1998. URL: https://doi.org/10.1145/278298.278306.
  3. 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.
  4. 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.
  5. Lijie Chen and Roei Tell. Hardness vs randomness, revised: Uniform, non-black-box, and instance-wise. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 125-136, 2022. URL: https://doi.org/10.1109/FOCS52979.2021.00021.
  6. Joshua Cook. More verifier efficient interactive protocols for bounded space, 2022. URL: https://eccc.weizmann.ac.il/report/2022/093/.
  7. Oded Goldreich. On doubly-efficient interactive proof systems, 2018. URL: https://www.wisdom.weizmann.ac.il/~oded/de-ip.html.
  8. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. Verifying and decoding in constant depth. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 440-449. Association for Computing Machinery, 2007. URL: https://doi.org/10.1145/1250790.1250855.
  9. 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.
  10. Neil Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5):935-938, 1988. URL: https://doi.org/10.1137/0217058.
  11. 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.
  12. Or Meir. IP = PSPACE using error-correcting codes. SIAM Journal on Computing, 42(1):380-403, 2013. URL: https://doi.org/10.1137/110829660.
  13. Dana Moshkovitz and Joshua Cook. Tighter ma/1 circuit lower bounds from verifier efficient pcps for pspace, 2022. URL: https://eccc.weizmann.ac.il/report/2022/014/.
  14. 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.
  15. Noam Nisan. Pseudorandom generators for space-bounded computations. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC '90, pages 204-212. Association for Computing Machinery, 1990. URL: https://doi.org/10.1145/100216.100242.
  16. 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.
  17. Noga Ron-Zewi and Ron D. Rothblum. Proving as fast as computing: Succinct arguments with constant prover overhead. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1353-1363. Association for Computing Machinery, 2022. URL: https://doi.org/10.1145/3519935.3519956.
  18. Michael Saks and Shiyu Zhou. BP_HSPACE(S)⊆DSPACE(S^3/2). J. Comput. Syst. Sci., 58(2):376-403, April 1999. URL: https://doi.org/10.1006/jcss.1998.1616.
  19. 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.
  20. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, April 1970. URL: https://doi.org/10.1016/S0022-0000(70)80006-X.
  21. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, October 1992. URL: https://doi.org/10.1145/146585.146609.
  22. A. Shen. IP = SPACE: Simplified Proof. J. ACM, 39(4):878-880, 1992. URL: https://doi.org/10.1145/146585.146613.
  23. Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279-284, 1988. URL: https://doi.org/10.1007/BF00299636.
  24. 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
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