Document Open Access Logo

Verifiable Stream Computation and Arthur–Merlin Communication

Authors Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.217.pdf
  • Filesize: 0.69 MB
  • 27 pages

Document Identifiers

Author Details

Amit Chakrabarti
Graham Cormode
Andrew McGregor
Justin Thaler
Suresh Venkatasubramanian

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 217-243, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.217

Abstract

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling to blindly trust answers returned by this service. Thus, the service cannot simply supply the desired answer; it must convince the verifier of its correctness via a short interaction after the stream has been seen.

In this work we study "barely interactive" SIPs. Specifically, we show that two or three rounds of interaction suffice to solve several query problems - including Index, Median, Nearest Neighbor Search, Pattern Matching, and Range Counting - with polylogarithmic space and communication costs. Such efficiency with O(1) rounds of interaction was thought to be impossible based on previous work.

On the other hand, we initiate a formal study of the limitations of constant-round SIPs by introducing a new hierarchy of communication models called Online Interactive Proofs (OIPs). The online nature of these models is analogous to the streaming restriction placed upon the verifier in an SIP. We give upper and lower bounds that (1) characterize, up to quadratic blowups, every finite level of the OIP hierarchy in terms of other well-known communication complexity classes, (2) separate the first four levels of the hierarchy, and (3) reveal that the hierarchy collapses to the fourth level. Our study of OIPs reveals marked contrasts and some parallels with the classic Turing Machine theory of interactive proofs, establishes limits on the power of existing techniques for developing constant-round SIPs, and provides a new characterization of (non-online) Arthur-Merlin communication in terms of an online model.

Subject Classification

Keywords
  • Arthur-Merlin communication complexity
  • streaming interactive proofs

Metrics

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

References

  1. Scott Aaronson. Qma/qpoly ⊆ pspace/poly: De-merlinizing quantum protocols. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 261-273. IEEE Computer Society, 2006. Google Scholar
  2. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. TOCT, 1(1), 2009. Google Scholar
  3. Farid Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science, 175(2):139-159, 1996. Google Scholar
  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. Google Scholar
  5. Laszlo Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In Foundations of Computer Science, 1986., 27th Annual Symposium on, pages 337-347, Oct 1986. Google Scholar
  6. László Babai and Shlomo Moran. Arthur-merlin games: A randomized proof system, and a hierarchy of complexity class. J. Comput. Syst. Sci., 36(2):254-276, April 1988. Google Scholar
  7. Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public key encryption with keyword search. In Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 506-522. Springer, 2004. Google Scholar
  8. 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. Google Scholar
  9. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in data streams. ACM Transactions on Algorithms, 11(1):7, 2014. A preliminary version of this paper by A. Chakrabarti, G. Cormode, and A. McGregor appeared in ICALP 2009. Google Scholar
  10. Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz. Memory delegation. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 151-168. Springer, 2011. Google Scholar
  11. Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild. From coding theory to efficient pattern matching. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 778-784. SIAM, 2009. Google Scholar
  12. A. Condon. The complexity of space bounded interactive proof systems, 1993. Google Scholar
  13. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 90-112. ACM, 2012. Google Scholar
  14. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming graph computations with a helpful advisor. Algorithmica, 65(2):409-442, 2013. Google Scholar
  15. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. PVLDB, 5(1):25-36, 2011. Google Scholar
  16. S Goldwasser and M Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC'86, pages 59-68, New York, NY, USA, 1986. ACM. Google Scholar
  17. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. A (de)constructive approach to program checking. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC'08, pages 143-152, New York, NY, USA, 2008. ACM. Google Scholar
  18. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC'08, pages 113-122, New York, NY, USA, 2008. ACM. Google Scholar
  19. Tom Gur and Ran Raz. Arthur-merlin streaming complexity. In FedorV. Fomin, Rusins Freivalds, Marta Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming, volume 7965 of Lecture Notes in Computer Science, pages 528-539. Springer Berlin Heidelberg, 2013. Google Scholar
  20. Adam Kalai. Efficient pattern-matching with don't cares. In David Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 655-656. ACM/SIAM, 2002. Google Scholar
  21. Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM J. Discret. Math., 5(4):545-557, November 1992. Google Scholar
  22. 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. Google Scholar
  23. 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. IEEE Computer Society, 2011. Google Scholar
  24. Hartmut Klauck and Ved Prakash. Streaming computations with a loquacious prover. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS'13, pages 305-320, New York, NY, USA, 2013. ACM. Google Scholar
  25. Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC'95, pages 596-605, New York, NY, USA, 1995. ACM. Google Scholar
  26. Satyanarayana V. Lokam. Spectral methods for matrix rigidity with applications to size–depth trade-offs and communication complexity. Journal of Computer and System Sciences, 63(3):449-473, 2001. Google Scholar
  27. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, October 1992. Google Scholar
  28. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005. Google Scholar
  29. Ilan Newman and Mario Szegedy. Public vs. private coin flips in one round communication games (extended abstract). In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 561-570. ACM, 1996. Google Scholar
  30. Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC'91, pages 419-429, New York, NY, USA, 1991. ACM. Google Scholar
  31. Y. Ofman. On the algorithmic complexity of discrete functions. Doklady Akademii Nauk SSSR, 145:48-51, 1962. English Translation in Soviet Physics Doklady 7: 589-591, 1963. Google Scholar
  32. Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi. Streaming authenticated data structures. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 353-370. Springer, 2013. Google Scholar
  33. Ran Raz. Quantum information and the PCP theorem. Algorithmica, 55(3):462-489, 2009. Google Scholar
  34. Dominique Schröder and Heike Schröder. Verifiable data streaming. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16-18, 2012, pages 953-964. ACM, 2012. Google Scholar
  35. Justin Thaler. Time-optimal interactive proofs for circuit evaluation. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II, volume 8043 of Lecture Notes in Computer Science, pages 71-89. Springer, 2013. Google Scholar
  36. Victor Vu, Srinath T. V. Setty, Andrew J. Blumberg, and Michael Walfish. A hybrid architecture for interactive verifiable computation. In 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19-22, 2013, pages 223-237. IEEE Computer Society, 2013. Google Scholar
  37. C.S. Wallace. A suggestion for a fast multiplier. Electronic Computers, IEEE Transactions on, EC-13(1):14-17, Feb 1964. 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