[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Non-interactive proofs of proximity

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

We initiate a study of non-interactive proofs of proximity. These proof systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire input, we only require it to reject inputs that are far from being valid. Thus, the verifier is only assured of the proximity of the statement to a correct one. Such proof systems can be viewed as the \({\mathcal{NP}}\) (or more accurately \({\mathcal{MA}}\)) analogue of property testing.

We explore both the power and limitations of non-interactive proofs of proximity. We show that such proof systems can be exponentially stronger than property testers, but are exponentially weaker than the interactive proofs of proximity studied by Rothblum, Vadhan and Wigderson (STOC 2013). In addition, we show a natural problem that has a full and (almost) tight multiplicative trade-off between the length of the proof and the verifier’s query complexity. On the negative side, we also show that there exist properties for which even a linearly long (non-interactive) proof of proximity cannot significantly reduce the query complexity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Bibliography

  • Scott Aaronson & Avi Wigderson (2009). Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory 1, 2:1–2:54. ISSN 1942-3454. URL http://doi.acm.org/10.1145/1490270.1490272.

  • Noga Alon, Eldar Fischer, Ilan Newman & Asaf Shapira (2006). A combinatorial characterization of the testable graph properties: it’s all about regularity. SIAM Journal on Computing 39(1), 143–167.

  • Alon Noga, Krivelevich Michael, Newman Ilan, Szegedy Mario (2000) Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput. 30(6): 1842–1862

    Article  MathSciNet  MATH  Google Scholar 

  • Arora Sanjeev, Sudan Madhu (2003) Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365–426

    Article  MathSciNet  MATH  Google Scholar 

  • László Babai (1985). Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, 421–429. ACM.

  • László Babai, Lance Fortnow, Leonid A. Levin & Mario Szegedy (1991). Checking Computations in Polylogarithmic Time. In: Proceedings of the twenty-third annual ACM symposium on Theory of computing, 21–32. ACM

  • Laszlo Babai, Peter Frankl & Janos Simon (1986). Complexity classes in communication complexity theory. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 337–347. IEEE Computer Society, Washington, DC, USA. ISBN 0-8186-0740-8. URL http://dl.acm.org/citation.cfm?id=1382439.1382962.

  • Ziv Bar-Yossef, Ravi Kumar & D. Sivakumar (2001). Sampling algorithms: lower bounds and applications. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing, 266–275. ACM

  • Ben-Sasson Eli, Goldreich Oded, Harsha Prahladh, Sudan Madhu, Vadhan Salil P. (2006) Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. 36(4): 889–974

    Article  MathSciNet  MATH  Google Scholar 

  • Eric Blais (2010). Testing Juntas: A Brief Survey. In Goldreich (2010a), 32–40.

  • Eric Blais, Joshua Brody & Kevin Matulef (2011). Property Testing Lower Bounds via Communication Complexity. In IEEE Conference on Computational Complexity, 210–220.

  • Andrej Bogdanov & Luca Trevisan (2004). Lower Bounds for Testing Bipartiteness in Dense Graphs. In IEEE Conference on Computational Complexity, 75–81.

  • Harry Buhrman & Ronald de Wolf (2002). Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21–43.

  • Canetti Ran, Even Guy, Goldreich Oded (1995) Lower Bounds for Sampling Algorithms for Estimating the Average. Inf. Process. Lett. 53(1): 17–25

    Article  MathSciNet  MATH  Google Scholar 

  • Amit Chakrabarti, Graham Cormode, Navin Goyal & Justin Thaler (2014a). Annotations for sparse data streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 687–706. SIAM.

  • Amit Chakrabarti, Graham Cormode, Andrew McGregor & Justin Thaler (2014b). Annotations in data streams. ACM Transactions on Algorithms (TALG) 11(1), 7.

  • Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler & Suresh Venkatasubramanian (2015). Verifiable Stream Computation and Arthur–Merlin Communication. In 30th Conference on Computational Complexity (CCC 2015), volume 33, 217–243. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

  • Amit Chakrabarti & Oded Regev (2011). An optimal lower bound on the communication complexity of gap-hamming-distance. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC ’11, 51–60. ACM, New York, NY, USA. ISBN 978-1-4503-0691-1. URL http://doi.acm.org/10.1145/1993636.1993644.

  • Graham Cormode, Michael Mitzenmacher & Justin Thaler (2012). Practical verified computation with streaming interactive proofs. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 90–112. ACM.

  • Cormode Graham, Mitzenmacher Michael, Justin Thaler (2013) Streaming graph computations with a helpful advisor. Algorithmica 65(2): 409–442

    Article  MathSciNet  MATH  Google Scholar 

  • Artur Czumaj, Oded Goldreich, Dana Ron, C Seshadhri, Asaf Shapira & Christian Sohler (2012). Finding cycles and trees in sublinear time. Random Structures & Algorithms.

  • Samira Daruki, Justin Thaler & Suresh Venkatasubramanian (2015). Streaming Verification in Data Analysis. arXiv preprint arXiv:1509.05514.

  • Dinur Irit, Reingold Omer (2006) Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM J. Comput. 36(4): 975–1024

    Article  MathSciNet  MATH  Google Scholar 

  • Ergün Funda, Kumar Ravi, Rubinfeld Ronitt (2004) Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135–159

    Article  MathSciNet  MATH  Google Scholar 

  • Eldar Fischer, Yonatan Goldhirsh & Oded Lachish (2014). Partial tests, universal tests and decomposability. In Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, 483–500. URL http://doi.acm.org/10.1145/2554797.2554841.

  • Fischer Eldar, Lachish Oded, Matsliah Arie, Newman Ilan, Yahalom Orly (2012) On the query complexity of testing orientations for being Eulerian. ACM Transactions on Algorithms 8(2): 15

    Article  MathSciNet  MATH  Google Scholar 

  • Dmitry Gavinsky & Alexander A Sherstov (2010). A separation of NP and coNP in multiparty communication complexity. arXiv preprint arXiv:1004.0817.

  • Gemmell Peter, Sudan Madhu (1992) Highly Resilient Correctors for Polynomials. Inf. Process. Lett. 43(4): 169–174

    Article  MathSciNet  MATH  Google Scholar 

  • Lior Gishboliner & Asaf Shapira (2013). Deterministic vs Non-deterministic Graph Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 20, 59.

  • Oded Goldreich (2008). Computational complexity - a conceptual perspective. Cambridge University Press. ISBN 978-0-521-88473-0, I-XXIV, 1-606.

  • Oded Goldreich (editor) (2010a). Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science. Springer. ISBN 978-3-642-16366-1.

  • Oded Goldreich (2010b). Short Locally Testable Codes and Proofs: A Survey in Two Parts. In Goldreich (2010a), 65–104.

  • Oded Goldreich (2011). Introduction to testing graph properties. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 470–506. Springer.

  • Oded Goldreich (2013). On Multiple Input Problems in Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 20, 67.

  • Goldreich Oded, Goldwasser Shafi, Ron Dana (1998) Property testing and its connection to learning and approximation. Journal of the ACM (JACM) 45(4): 653–750

    Article  MathSciNet  MATH  Google Scholar 

  • Oded Goldreich & Tom Gur (2016). Universal Locally Testable Codes. Electronic Colloquium on Computational Complexity (ECCC) 23, 42. URL http://eccc.hpi-web.de/report/2016/042.

  • Oded Goldreich, Tom Gur & Ilan Komargodski (2014). Strong Locally Testable Codes with Relaxed Local Decoders. Electronic Colloquium on Computational Complexity (ECCC) 21, 25.

  • Oded Goldreich, Tom Gur & Ron D. Rothblum (2015). 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, 666–677. URL http://dx.doi.org/10.1007/978-3-662-47672-7_54.

  • Goldreich Oded, Håstad Johan (1998) On the complexity of interactive proofs with bounded communication. Information Processing Letters 67(4): 205–214

    Article  MathSciNet  MATH  Google Scholar 

  • Goldreich Oded, Krawczyk Hugo (1992) Sparse Pseudorandom Distributions. Random Struct. Algorithms 3(2): 163–174

    Article  MathSciNet  MATH  Google Scholar 

  • Goldreich Oded, Ron Dana (1999) A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19(3): 335–373

    Article  MathSciNet  MATH  Google Scholar 

  • Goldreich Oded, Ron Dana (2002) Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302–343

    Article  MathSciNet  MATH  Google Scholar 

  • Goldreich Oded, Ron Dana (2011) On Proximity-Oblivious Testing. SIAM Journal on Computing 40(2): 534–566

    Article  MathSciNet  MATH  Google Scholar 

  • Oded Goldreich & Dana Ron (2013). On Sample-Based Testers. Electronic Colloquium on Computational Complexity (ECCC) 20, 109.

  • Oded Goldreich & Dana Ron (2014). On Learning and Testing Dynamic Environments. Electronic Colloquium on Computational Complexity (ECCC) 21, 29.

  • Oded Goldreich & Or Sheffet (2010). On The Randomness Complexity of Property Testing. Computational Complexity 19(1), 99–133.

  • Oded Goldreich & Igor Shinkar (2012). Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). In APPROX-RANDOM, 565–578.

  • Goldreich Oded, Sudan Madhu (2006) Locally testable codes and PCPs of almost-linear length. J. ACM 53(4): 558–655

    Article  MathSciNet  MATH  Google Scholar 

  • Goldreich Oded, Vadhan Salil, Wigderson Avi (2002) On interactive proofs with a laconic prover. Computational Complexity 11(1-2): 1–53

    Article  MathSciNet  MATH  Google Scholar 

  • Goldwasser Shafi, Micali Silvio, Rackoff Charles (1989) The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput. 18(1): 186–208

    Article  MathSciNet  MATH  Google Scholar 

  • Tom Gur & Ran Raz (2013). Arthur-Merlin Streaming Complexity. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP).

  • Tom Gur & Ron Rothblum (2013). Non-Interactive Proofs of Proximity. Electronic Colloquium on Computational Complexity (ECCC) 20, 78.

  • Tom Gur & Ron D. Rothblum (2015). Non-Interactive Proofs of Proximity. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, 133–142. URL http://doi.acm.org/10.1145/2688073.2688079.

  • Shirley Halevy, Oded Lachish, Ilan Newman & Dekel Tsur (2005). Testing Orientation Properties. Electronic Colloquium on Computational Complexity (ECCC).

  • Shirley Halevy, Oded Lachish, Ilan Newman & Dekel Tsur (2007). Testing Properties of Constraint-Graphs. In IEEE Conference on Computational Complexity, 264–277.

  • Yael Tauman Kalai & Ron D. Rothblum (2015). 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, 422–442. URL http://dx.doi.org/10.1007/978-3-662-48000-7_21.

  • Kalyanasundaram Bala, Schintger Georg (1992) The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics 5(4): 545–557

    Article  MathSciNet  MATH  Google Scholar 

  • Jonathan Katz & Luca Trevisan (2000). On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp 80–86, ACM.

  • Tali Kaufman & Madhu Sudan (2008). Algebraic property testing: the role of invariance. In Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC), 403–412. ACM.

  • Hartmut Klauck (2003). Rectangle size bounds and threshold covers in communication complexity. In Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on, 118–134. IEEE.

  • Hartmut Klauck (2011). On Arthur Merlin Games in Communication Complexity. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, 189–199. IEEE.

  • Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press. ISBN 978-0-521-56067-2, I-XIII, 1-189.

  • Lautemann Clemens (1983) BPP and the Polynomial Hierarchy. Inf. Process. Lett. 17(4): 215–217

    Article  MathSciNet  MATH  Google Scholar 

  • Leonid A. Levin (1987). One way functions and pseudorandom generators. Combinatorica 7(4), 357–363.

  • László Lovász & Katalin Vesztergombi (2012). Nondeterministic graph property testing. arXiv preprint arXiv:1202.5337.

  • Lund Carsten, Fortnow Lance, Karloff Howard J., Nisan Noam (1992) Algebraic Methods for Interactive Proof Systems. J. ACM 39(4): 859–868

    Article  MathSciNet  MATH  Google Scholar 

  • Newman Ilan (1991) Private vs. common random bits in communication complexity. Information processing letters 39(2): 67–71

    Article  MathSciNet  MATH  Google Scholar 

  • Ilan Newman (2010). Property testing of massively parametrized problems -a survey. In Property testing: current research and surveys, 142–157. Springer.

  • Christos H Papadimitriou & Mihalis Yannakakis (1996). On limited nondeterminism and the complexity of the VC dimension. Journal of Computer and System Sciences 53(2), 161–170.

  • Ron Dana (2008) Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3): 307–402

    Article  MATH  Google Scholar 

  • Ron Dana (2009) Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science 5(2): 73–205

    Article  MathSciNet  MATH  Google Scholar 

  • Guy N. Rothblum, Salil Vadhan & Avi Wigderson (2013). Interactive Proofs of Proximity: Delegating Computation in Sublinear Time. In Proceedings of the 45th annual ACM Symposium on Theory of Computing (STOC).

  • Rubinfeld Ronitt, Sudan Madhu (1996) Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252–271

    Article  MathSciNet  MATH  Google Scholar 

  • Alexander A Sherstov (2012). The multiparty communication complexity of set disjointness. In Proceedings of the 44th Symposium on Theory of Computing, 525–548. ACM.

  • Madhu Sudan (1995). Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems, volume 1001 of Lecture Notes in Computer Science. Springer. ISBN 3-540-60615-7.

  • Justin Thaler (2014). Semi-Streaming Algorithms for Annotated Graph Streams. arXiv preprint arXiv:1407.3462.

Download references

Author information

Authors and Affiliations

  1. Weizmann Institute, Rehovot, Israel

    Tom Gur

  2. MIT, Cambridge, MA, USA

    Ron D. Rothblum

Authors
  1. Tom Gur
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ron D. Rothblum
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tom Gur.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gur, T., Rothblum, R.D. Non-interactive proofs of proximity. comput. complex. 27, 99–207 (2018). https://doi.org/10.1007/s00037-016-0136-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00037-016-0136-9

Keywords

Subject classification

Search

Navigation