{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:48Z","timestamp":1781078268702,"version":"3.54.1"},"reference-count":76,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,6,3]],"date-time":"2016-06-03T00:00:00Z","timestamp":1464912000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00037-016-0136-9","type":"journal-article","created":{"date-parts":[[2016,6,3]],"date-time":"2016-06-03T02:41:59Z","timestamp":1464921719000},"page":"99-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Non-interactive proofs of proximity"],"prefix":"10.1007","volume":"27","author":[{"given":"Tom","family":"Gur","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,6,3]]},"reference":[{"key":"136_CR1","unstructured":"Scott Aaronson & Avi Wigderson (2009). Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory 1, 2:1\u20132:54. ISSN 1942-3454. URL http:\/\/doi.acm.org\/10.1145\/1490270.1490272 ."},{"key":"136_CR2","doi-asserted-by":"crossref","unstructured":"Noga Alon, Eldar Fischer, Ilan Newman & Asaf Shapira (2006). A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. SIAM Journal on Computing 39(1), 143\u2013167.","DOI":"10.1137\/060667177"},{"issue":"6","key":"136_CR3","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1137\/S0097539700366528","volume":"30","author":"Noga Alon","year":"2000","unstructured":"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\u20131862","journal-title":"SIAM J. Comput."},{"issue":"3","key":"136_CR4","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"Sanjeev Arora","year":"2003","unstructured":"Arora Sanjeev, Sudan Madhu (2003) Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365\u2013426","journal-title":"Combinatorica"},{"key":"136_CR5","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai (1985). Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, 421\u2013429. ACM.","DOI":"10.1145\/22145.22192"},{"key":"136_CR6","unstructured":"L\u00e1szl\u00f3 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\u201332. ACM"},{"key":"136_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013347. IEEE Computer Society, Washington, DC, USA. ISBN 0-8186-0740-8. URL http:\/\/dl.acm.org\/citation.cfm?id=1382439.1382962 .","DOI":"10.1109\/SFCS.1986.15"},{"key":"136_CR8","doi-asserted-by":"crossref","unstructured":"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\u2013275. ACM","DOI":"10.1145\/380752.380810"},{"issue":"4","key":"136_CR9","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"Eli Ben-Sasson","year":"2006","unstructured":"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\u2013974","journal-title":"SIAM J. Comput."},{"key":"136_CR10","doi-asserted-by":"crossref","unstructured":"Eric Blais (2010). Testing Juntas: A Brief Survey. In Goldreich (2010a), 32\u201340.","DOI":"10.1007\/978-3-642-16367-8_4"},{"key":"136_CR11","doi-asserted-by":"crossref","unstructured":"Eric Blais, Joshua Brody & Kevin Matulef (2011). Property Testing Lower Bounds via Communication Complexity. In IEEE Conference on Computational Complexity, 210\u2013220.","DOI":"10.1109\/CCC.2011.31"},{"key":"136_CR12","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Luca Trevisan (2004). Lower Bounds for Testing Bipartiteness in Dense Graphs. In IEEE Conference on Computational Complexity, 75\u201381.","DOI":"10.1109\/CCC.2004.1313803"},{"key":"136_CR13","doi-asserted-by":"crossref","unstructured":"Harry Buhrman & Ronald de Wolf (2002). Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343.","DOI":"10.1016\/S0304-3975(01)00144-X"},{"issue":"1","key":"136_CR14","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0020-0190(94)00171-T","volume":"53","author":"Ran Canetti","year":"1995","unstructured":"Canetti Ran, Even Guy, Goldreich Oded (1995) Lower Bounds for Sampling Algorithms for Estimating the Average. Inf. Process. Lett. 53(1): 17\u201325","journal-title":"Inf. Process. Lett."},{"key":"136_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013706. SIAM.","DOI":"10.1137\/1.9781611973402.52"},{"key":"136_CR16","doi-asserted-by":"crossref","unstructured":"Amit Chakrabarti, Graham Cormode, Andrew McGregor & Justin Thaler (2014b). Annotations in data streams. ACM Transactions on Algorithms (TALG) 11(1), 7.","DOI":"10.1145\/2636924"},{"key":"136_CR17","unstructured":"Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler & Suresh Venkatasubramanian (2015). Verifiable Stream Computation and Arthur\u2013Merlin Communication. In 30th Conference on Computational Complexity (CCC 2015), volume 33, 217\u2013243. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik."},{"key":"136_CR18","doi-asserted-by":"crossref","unstructured":"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 \u201911, 51\u201360. ACM, New York, NY, USA. ISBN 978-1-4503-0691-1. URL http:\/\/doi.acm.org\/10.1145\/1993636.1993644 .","DOI":"10.1145\/1993636.1993644"},{"key":"136_CR19","doi-asserted-by":"crossref","unstructured":"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\u2013112. ACM.","DOI":"10.1145\/2090236.2090245"},{"issue":"2","key":"136_CR20","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00453-011-9598-y","volume":"65","author":"Graham Cormode","year":"2013","unstructured":"Cormode Graham, Mitzenmacher Michael, Justin Thaler (2013) Streaming graph computations with a helpful advisor. Algorithmica 65(2): 409\u2013442","journal-title":"Algorithmica"},{"key":"136_CR21","unstructured":"Artur Czumaj, Oded Goldreich, Dana Ron, C Seshadhri, Asaf Shapira & Christian Sohler (2012). Finding cycles and trees in sublinear time. Random Structures & Algorithms."},{"key":"136_CR22","unstructured":"Samira Daruki, Justin Thaler & Suresh Venkatasubramanian (2015). Streaming Verification in Data Analysis. arXiv preprint arXiv:1509.05514 ."},{"issue":"4","key":"136_CR23","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"Irit Dinur","year":"2006","unstructured":"Dinur Irit, Reingold Omer (2006) Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM J. Comput. 36(4): 975\u20131024","journal-title":"SIAM J. Comput."},{"issue":"2","key":"136_CR24","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.ic.2003.09.005","volume":"189","author":"Funda Erg\u00fcn","year":"2004","unstructured":"Erg\u00fcn Funda, Kumar Ravi, Rubinfeld Ronitt (2004) Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135\u2013159","journal-title":"Inf. Comput."},{"key":"136_CR25","doi-asserted-by":"crossref","unstructured":"Eldar Fischer, Yonatan Goldhirsh & Oded Lachish (2014). Partial tests, universal tests and decomposability. In Innovations in Theoretical Computer Science, ITCS\u201914, Princeton, NJ, USA, January 12-14, 2014, 483\u2013500. URL http:\/\/doi.acm.org\/10.1145\/2554797.2554841 .","DOI":"10.1145\/2554797.2554841"},{"issue":"2","key":"136_CR26","first-page":"15","volume":"8","author":"Eldar Fischer","year":"2012","unstructured":"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","journal-title":"ACM Transactions on Algorithms"},{"key":"136_CR27","unstructured":"Dmitry Gavinsky & Alexander A Sherstov (2010). A separation of NP and coNP in multiparty communication complexity. arXiv preprint arXiv:1004.0817 ."},{"issue":"4","key":"136_CR28","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(92)90195-2","volume":"43","author":"Peter Gemmell","year":"1992","unstructured":"Gemmell Peter, Sudan Madhu (1992) Highly Resilient Correctors for Polynomials. Inf. Process. Lett. 43(4): 169\u2013174","journal-title":"Inf. Process. Lett."},{"key":"136_CR29","unstructured":"Lior Gishboliner & Asaf Shapira (2013). Deterministic vs Non-deterministic Graph Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 20, 59."},{"key":"136_CR30","unstructured":"Oded Goldreich (2008). Computational complexity - a conceptual perspective. Cambridge University Press. ISBN 978-0-521-88473-0, I-XXIV, 1-606."},{"key":"136_CR31","unstructured":"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."},{"key":"136_CR32","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2010b). Short Locally Testable Codes and Proofs: A Survey in Two Parts. In Goldreich (2010a), 65\u2013104.","DOI":"10.1007\/978-3-642-16367-8_6"},{"key":"136_CR33","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2011). Introduction to testing graph properties. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 470\u2013506. Springer.","DOI":"10.1007\/978-3-642-22670-0_32"},{"key":"136_CR34","unstructured":"Oded Goldreich (2013). On Multiple Input Problems in Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 20, 67."},{"issue":"4","key":"136_CR35","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"Oded Goldreich","year":"1998","unstructured":"Goldreich Oded, Goldwasser Shafi, Ron Dana (1998) Property testing and its connection to learning and approximation. Journal of the ACM (JACM) 45(4): 653\u2013750","journal-title":"Journal of the ACM (JACM)"},{"key":"136_CR36","unstructured":"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 ."},{"key":"136_CR37","unstructured":"Oded Goldreich, Tom Gur & Ilan Komargodski (2014). Strong Locally Testable Codes with Relaxed Local Decoders. Electronic Colloquium on Computational Complexity (ECCC) 21, 25."},{"key":"136_CR38","doi-asserted-by":"crossref","unstructured":"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\u2013677. URL http:\/\/dx.doi.org\/10.1007\/978-3-662-47672-7_54 .","DOI":"10.1007\/978-3-662-47672-7_54"},{"issue":"4","key":"136_CR39","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"Oded Goldreich","year":"1998","unstructured":"Goldreich Oded, H\u00e5stad Johan (1998) On the complexity of interactive proofs with bounded communication. Information Processing Letters 67(4): 205\u2013214","journal-title":"Information Processing Letters"},{"issue":"2","key":"136_CR40","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1002\/rsa.3240030206","volume":"3","author":"Oded Goldreich","year":"1992","unstructured":"Goldreich Oded, Krawczyk Hugo (1992) Sparse Pseudorandom Distributions. Random Struct. Algorithms 3(2): 163\u2013174","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"136_CR41","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"Oded Goldreich","year":"1999","unstructured":"Goldreich Oded, Ron Dana (1999) A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19(3): 335\u2013373","journal-title":"Combinatorica"},{"issue":"2","key":"136_CR42","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"Oded Goldreich","year":"2002","unstructured":"Goldreich Oded, Ron Dana (2002) Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302\u2013343","journal-title":"Algorithmica"},{"issue":"2","key":"136_CR43","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1137\/100789646","volume":"40","author":"Oded Goldreich","year":"2011","unstructured":"Goldreich Oded, Ron Dana (2011) On Proximity-Oblivious Testing. SIAM Journal on Computing 40(2): 534\u2013566","journal-title":"SIAM Journal on Computing"},{"key":"136_CR44","unstructured":"Oded Goldreich & Dana Ron (2013). On Sample-Based Testers. Electronic Colloquium on Computational Complexity (ECCC) 20, 109."},{"key":"136_CR45","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Dana Ron (2014). On Learning and Testing Dynamic Environments. Electronic Colloquium on Computational Complexity (ECCC) 21, 29.","DOI":"10.1109\/FOCS.2014.43"},{"key":"136_CR46","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Or Sheffet (2010). On The Randomness Complexity of Property Testing. Computational Complexity 19(1), 99\u2013133.","DOI":"10.1007\/s00037-009-0282-4"},{"key":"136_CR47","unstructured":"Oded Goldreich & Igor Shinkar (2012). Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). In APPROX-RANDOM, 565\u2013578."},{"issue":"4","key":"136_CR48","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/1162349.1162351","volume":"53","author":"Oded Goldreich","year":"2006","unstructured":"Goldreich Oded, Sudan Madhu (2006) Locally testable codes and PCPs of almost-linear length. J. ACM 53(4): 558\u2013655","journal-title":"J. ACM"},{"issue":"1-2","key":"136_CR49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"Oded Goldreich","year":"2002","unstructured":"Goldreich Oded, Vadhan Salil, Wigderson Avi (2002) On interactive proofs with a laconic prover. Computational Complexity 11(1-2): 1\u201353","journal-title":"Computational Complexity"},{"issue":"1","key":"136_CR50","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"Shafi Goldwasser","year":"1989","unstructured":"Goldwasser Shafi, Micali Silvio, Rackoff Charles (1989) The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput. 18(1): 186\u2013208","journal-title":"SIAM J. Comput."},{"key":"136_CR51","doi-asserted-by":"crossref","unstructured":"Tom Gur & Ran Raz (2013). Arthur-Merlin Streaming Complexity. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP).","DOI":"10.1007\/978-3-642-39206-1_45"},{"key":"136_CR52","unstructured":"Tom Gur & Ron Rothblum (2013). Non-Interactive Proofs of Proximity. Electronic Colloquium on Computational Complexity (ECCC) 20, 78."},{"key":"136_CR53","unstructured":"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\u2013142. URL http:\/\/doi.acm.org\/10.1145\/2688073.2688079 ."},{"key":"136_CR54","unstructured":"Shirley Halevy, Oded Lachish, Ilan Newman & Dekel Tsur (2005). Testing Orientation Properties. Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"136_CR55","doi-asserted-by":"crossref","unstructured":"Shirley Halevy, Oded Lachish, Ilan Newman & Dekel Tsur (2007). Testing Properties of Constraint-Graphs. In IEEE Conference on Computational Complexity, 264\u2013277.","DOI":"10.1109\/CCC.2007.31"},{"key":"136_CR56","doi-asserted-by":"crossref","unstructured":"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\u2013442. URL http:\/\/dx.doi.org\/10.1007\/978-3-662-48000-7_21 .","DOI":"10.1007\/978-3-662-48000-7_21"},{"issue":"4","key":"136_CR57","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"Bala Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram Bala, Schintger Georg (1992) The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics 5(4): 545\u2013557","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"136_CR58","doi-asserted-by":"crossref","unstructured":"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\u201386, ACM.","DOI":"10.1145\/335305.335315"},{"key":"136_CR59","doi-asserted-by":"crossref","unstructured":"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\u2013412. ACM.","DOI":"10.1145\/1374376.1374434"},{"key":"136_CR60","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2003). Rectangle size bounds and threshold covers in communication complexity. In Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on, 118\u2013134. IEEE.","DOI":"10.1109\/CCC.2003.1214415"},{"key":"136_CR61","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2011). On Arthur Merlin Games in Communication Complexity. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, 189\u2013199. IEEE.","DOI":"10.1109\/CCC.2011.33"},{"key":"136_CR62","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press. ISBN 978-0-521-56067-2, I-XIII, 1-189.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"issue":"4","key":"136_CR63","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"Clemens Lautemann","year":"1983","unstructured":"Lautemann Clemens (1983) BPP and the Polynomial Hierarchy. Inf. Process. Lett. 17(4): 215\u2013217","journal-title":"Inf. Process. Lett."},{"key":"136_CR64","doi-asserted-by":"crossref","unstructured":"Leonid A. Levin (1987). One way functions and pseudorandom generators. Combinatorica 7(4), 357\u2013363.","DOI":"10.1007\/BF02579323"},{"key":"136_CR65","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz & Katalin Vesztergombi (2012). Nondeterministic graph property testing. arXiv preprint arXiv:1202.5337 ."},{"issue":"4","key":"136_CR66","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"Carsten Lund","year":"1992","unstructured":"Lund Carsten, Fortnow Lance, Karloff Howard J., Nisan Noam (1992) Algebraic Methods for Interactive Proof Systems. J. ACM 39(4): 859\u2013868","journal-title":"J. ACM"},{"issue":"2","key":"136_CR67","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"Ilan Newman","year":"1991","unstructured":"Newman Ilan (1991) Private vs. common random bits in communication complexity. Information processing letters 39(2): 67\u201371","journal-title":"Information processing letters"},{"key":"136_CR68","doi-asserted-by":"crossref","unstructured":"Ilan Newman (2010). Property testing of massively parametrized problems -a survey. In Property testing: current research and surveys, 142\u2013157. Springer.","DOI":"10.1007\/978-3-642-16367-8_8"},{"key":"136_CR69","doi-asserted-by":"crossref","unstructured":"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\u2013170.","DOI":"10.1006\/jcss.1996.0058"},{"issue":"3","key":"136_CR70","first-page":"307","volume":"1","author":"Dana Ron","year":"2008","unstructured":"Ron Dana (2008) Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3): 307\u2013402","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"2","key":"136_CR71","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"Dana Ron","year":"2009","unstructured":"Ron Dana (2009) Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science 5(2): 73\u2013205","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"136_CR72","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1145\/2488608.2488709"},{"issue":"2","key":"136_CR73","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"Ronitt Rubinfeld","year":"1996","unstructured":"Rubinfeld Ronitt, Sudan Madhu (1996) Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252\u2013271","journal-title":"SIAM J. Comput."},{"key":"136_CR74","doi-asserted-by":"crossref","unstructured":"Alexander A Sherstov (2012). The multiparty communication complexity of set disjointness. In Proceedings of the 44th Symposium on Theory of Computing, 525\u2013548. ACM.","DOI":"10.1145\/2213977.2214026"},{"key":"136_CR75","unstructured":"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."},{"key":"136_CR76","unstructured":"Justin Thaler (2014). Semi-Streaming Algorithms for Annotated Graph Streams. arXiv preprint arXiv:1407.3462 ."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0136-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0136-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0136-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0136-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T02:40:27Z","timestamp":1567996827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0136-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,3]]},"references-count":76,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["136"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0136-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,3]]}}}