{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T08:33:01Z","timestamp":1694248381199},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T00:00:00Z","timestamp":1629244800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T00:00:00Z","timestamp":1629244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Interactive proofs of proximity allow a sublinear-time verifier to\n  check that a given input is <jats:italic>close<\/jats:italic> to the language, using a\n  small amount of communication with a powerful (but untrusted)\n  prover. In this work, we consider two natural\n  <jats:italic>minimally interactive<\/jats:italic> variants of such\n  proofs systems, in which the prover only sends a single message,\n  referred to as the proof.\n<\/jats:p><jats:p>The first variant, known as -proofs of\n  Proximity (), is fully <jats:italic>non-interactive<\/jats:italic>, meaning that the\n  proof is a function of the input <jats:italic>only<\/jats:italic>. The second variant,\n  known as -proofs of Proximity (), allows the proof\n  to additionally depend on the verifier's (entire) random string. The\n  complexity of both s and s is the total number of bits\n  that the verifier observes\u2014namely, the sum of the proof length\n  and query complexity.\n<\/jats:p><jats:p>Our main result is an exponential separation between the power of\n  s and s. Specifically, we exhibit an explicit and\n  natural property <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Pi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that admits an  with complexity\n  <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, whereas any  for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Pi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has complexity\n  <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\tilde{\\Omega}(n^{1\/4})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mover>\n                      <mml:mi>\u03a9<\/mml:mi>\n                      <mml:mo>~<\/mml:mo>\n                    <\/mml:mover>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mn>4<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>n<\/jats:italic> denotes the length of the input\n  in bits. Our  lower bound also yields an alternate proof,\n  which is more general and arguably much simpler, for a\n  recent result of Fischer et al. (ITCS, 2014). Also, Aaronson (<jats:italic>Quantum Information<\/jats:italic> &amp; <jats:italic>Computation<\/jats:italic> 2012) has shown\n  a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega(n^{1\/6})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>6<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound for the same property <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Pi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>Lastly, we also consider the notion of <jats:italic>oblivious<\/jats:italic>  proofs of proximity, in which\n  the verifier's queries are oblivious to the proof.\n  In this setting, we show\n  that s can only be quadratically stronger than s.  As an\n  application of this result, we show an exponential separation\n  between the power of public and private coin for oblivious\n  interactive proofs of proximity.<\/jats:p>","DOI":"10.1007\/s00037-021-00212-3","type":"journal-article","created":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T15:03:02Z","timestamp":1629298982000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Exponential Separation Between MA and AM Proofs of Proximity"],"prefix":"10.1007","volume":"30","author":[{"given":"Tom","family":"Gur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang P.","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,18]]},"reference":[{"key":"212_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson (2012). Impossibility of succinct quantum proofs\nfor collision-freeness. Quantum Information & Computation 12(1-\n2), 21\u201328. URL http:\/\/www.rintonpress.com\/xxqic12\/qic-12-12\/0021-0028.pdf.","DOI":"10.26421\/QIC12.1-2-3"},{"key":"212_CR2","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Avi Wigderson (2009). Algebrization: A New\nBarrier in Complexity Theory. TOCT 1(1), 2:1\u20132:54. URL http:\/\/doi.acm.org\/10.1145\/1490270.1490272.","DOI":"10.1145\/1490270.1490272"},{"key":"212_CR3","doi-asserted-by":"crossref","unstructured":"Amir Abboud, Aviad Rubinstein & R. Ryan Williams (2017).\nDistributed PCP Theorems for Hardness of Approximation in P. In\n58th IEEE Annual Symposium on Foundations of Computer Science,\nFOCS 2017, Berkeley, CA, USA, October 15-17, 2017, 25\u201336. URL\nhttps:\/\/doi.org\/10.1109\/FOCS.2017.12.","DOI":"10.1109\/FOCS.2017.12"},{"key":"212_CR4","unstructured":"Dorit Aharonov & Tomer Naveh (2002). Quantum NP-a survey.\narXiv preprint quant-ph\/0210077 ."},{"key":"212_CR5","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Peter Frankl & Janos Simon (1986). Complexity\nclasses in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October\n1986, 337\u2013347. URL https:\/\/doi.org\/10.1109\/SFCS.1986.15.","DOI":"10.1109\/SFCS.1986.15"},{"key":"212_CR6","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai & Shlomo Moran (1988). Arthur-Merlin Games: A\nRandomized Proof System, and a Hierarchy of Complexity Classes. J.\nComput. Syst. Sci. 36(2), 254\u2013276. URL https:\/\/doi.org\/10.1016\/0022-0000(88)90028-1.","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"212_CR7","doi-asserted-by":"crossref","unstructured":"Mihir Bellare & Moti Yung (1996). Certifying Permutations: Noninteractive\nZero-Knowledge Based on Any Trapdoor Permutation. J.\nCryptology 9(3), 149\u2013166.","DOI":"10.1007\/BF00208000"},{"key":"212_CR8","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu\nSudan & Salil P. Vadhan (2006). Robust PCPs of Proximity, Shorter\nPCPs, and Applications to Coding. SIAM J. Comput. 36(4), 889\u2013974.\nURL https:\/\/doi.org\/10.1137\/S0097539705446810.","DOI":"10.1137\/S0097539705446810"},{"key":"212_CR9","unstructured":"Itay Berman, Ron D. Rothblum & Vinod Vaikuntanathan\n(2017). Zero-Knowledge Proofs of Proximity. IACR Cryptology ePrint\nArchive 2017, 114. URL http:\/\/eprint.iacr.org\/2017\/114."},{"key":"212_CR10","doi-asserted-by":"crossref","unstructured":"Eric Blais, Joshua Brody & Kevin Matulef (2012). Property\nTesting Lower Bounds via Communication Complexity. Computational\nComplexity 21(2), 311\u2013358. URL https:\/\/doi.org\/10.1007\/s00037-012-0040-x.","DOI":"10.1007\/s00037-012-0040-x"},{"key":"212_CR11","doi-asserted-by":"crossref","unstructured":"Mark Braverman (2011). Poly-logarithmic independence fools\nbounded-depth boolean circuits. Commun. ACM 54(4), 108\u2013115. URL\nhttp:\/\/doi.acm.org\/10.1145\/1924421.1924446.","DOI":"10.1145\/1924421.1924446"},{"key":"212_CR12","unstructured":"Cl\u00e9ment L. Canonne (2015). A Survey on Distribution Testing: Your\nData is Big. But is it Blue? Electronic Colloquium on Computational\nComplexity (ECCC) 22, 63. URL http:\/\/eccc.hpi-web.de\/report\/2015\/063."},{"key":"212_CR13","doi-asserted-by":"crossref","unstructured":"Amit Chakrabarti, Graham Cormode, Andrew McGregor\n& Justin Thaler (2014). Annotations in Data Streams. ACM\nTrans. Algorithms 11(1), 7:1\u20137:30. URL http:\/\/doi.acm.org\/10.1145\/2636924.","DOI":"10.1145\/2636924"},{"key":"212_CR14","unstructured":"Amit Chakrabarti, Graham Cormode, Andrew McGregor,\nJustin Thaler & Suresh Venkatasubramanian (2015). Verifiable Stream Computation and Arthur-Merlin Communication. In 30th Conference\non Computational Complexity, CCC 2015, June 17-19, 2015,\nPortland, Oregon, USA, 217\u2013243. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2015.217."},{"key":"212_CR15","unstructured":"Alessandro Chiesa & Tom Gur (2017). Proofs of Proximity for\nDistribution Testing. ECCC 24, 155. URL https:\/\/eccc.weizmann.ac.il\/report\/2017\/155."},{"key":"212_CR16","doi-asserted-by":"crossref","unstructured":"Graham Cormode, Michael Mitzenmacher & Justin Thaler\n(2010). Streaming Graph Computations with a Helpful Advisor. In\nAlgorithms - ESA 2010, 18th Annual European Symposium, Liverpool,\nUK, September 6-8, 2010. Proceedings, Part I, 231\u2013242. URL https:\/\/doi.org\/10.1007\/978-3-642-15775-2_20.","DOI":"10.1007\/978-3-642-15775-2_20"},{"key":"212_CR17","doi-asserted-by":"crossref","unstructured":"Graham Cormode, Justin Thaler & Ke Yi (2011). Verifying\nComputations with Streaming Interactive Proofs. PVLDB 5(1), 25\u2013\n36. URL http:\/\/www.vldb.org\/pvldb\/vol5\/p025_grahamcormode_vldb2012.pdf.","DOI":"10.14778\/2047485.2047488"},{"key":"212_CR18","doi-asserted-by":"crossref","unstructured":"Irit Dinur & Omer Reingold (2006). Assignment Testers: Toward\na Combinatorial Proof of the PCP Theorem. SIAM J. Comput. 36(4),\n975\u20131024. URL https:\/\/doi.org\/10.1137\/S0097539705446962.","DOI":"10.1137\/S0097539705446962"},{"key":"212_CR19","doi-asserted-by":"crossref","unstructured":"Funda Erg\u00fcn, Ravi Kumar & Ronitt Rubinfeld (2004). Fast\napproximate probabilistically checkable proofs. Inf. Comput. 189(2),\n135\u2013159. URL https:\/\/doi.org\/10.1016\/j.ic.2003.09.005.","DOI":"10.1016\/j.ic.2003.09.005"},{"key":"212_CR20","doi-asserted-by":"crossref","unstructured":"Uriel Feige, Dror Lapidot & Adi Shamir (1999). Multiple Non-\nInteractive Zero Knowledge Proofs Under General Assumptions. SIAM\nJournal on Computing Preliminary version in FOCS\u201990.","DOI":"10.1137\/S0097539792230010"},{"key":"212_CR21","doi-asserted-by":"crossref","unstructured":"Eldar Fischer, Yonatan Goldhirsh & Oded Lachish (2014).\nPartial tests, universal tests and decomposability. In Innovations in\nTheoretical Computer Science, ITCS\u201914, Princeton, NJ, USA, January\n12-14, 2014, 483\u2013500. URL http:\/\/doi.acm.org\/10.1145\/2554797.2554841.","DOI":"10.1145\/2554797.2554841"},{"key":"212_CR22","doi-asserted-by":"crossref","unstructured":"Eldar Fischer, Oded Lachish & Yadu Vasudev (2015). Trading\nQuery Complexity for Sample-Based Testing and Multi-testing Scalability.\nIn IEEE 56th Annual Symposium on Foundations of Computer\nScience, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, 1163\u2013\n1182. URL https:\/\/doi.org\/10.1109\/FOCS.2015.75.","DOI":"10.1109\/FOCS.2015.75"},{"key":"212_CR23","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2017). Introduction to Property Testing. Cambridge\nUniversity Press. ISBN 978-1-107-19405-2.","DOI":"10.1017\/9781108135252"},{"key":"212_CR24","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property\nTesting and its Connection to Learning and Approximation. J.\nACM 45(4), 653\u2013750. URL http:\/\/doi.acm.org\/10.1145\/285055.285060.","DOI":"10.1145\/285055.285060"},{"key":"212_CR25","unstructured":"Oded Goldreich & Tom Gur (2016a). Universal Locally Testable\nCodes. Electronic Colloquium on Computational Complexity (ECCC)23, 42. URL http:\/\/eccc.hpi-web.de\/report\/2016\/042."},{"key":"212_CR26","unstructured":"Oded Goldreich & Tom Gur (2016b). Universal Locally Verifiable\nCodes and 3-Round Interactive Proofs of Proximity for CSP. Electronic\nColloquium on Computational Complexity (ECCC) 23, 192. URL\nhttp:\/\/eccc.hpi-web.de\/report\/2016\/192."},{"key":"212_CR27","unstructured":"Oded Goldreich, Tom Gur & Ilan Komargodski (2015a). Strong\nLocally Testable Codes with Relaxed Local Decoders. In 30th Conference\non Computational Complexity, CCC 2015, June 17-19, 2015, Portland,\nOregon, USA, 1\u201341. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2015.1."},{"key":"212_CR28","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Tom Gur & Ron D. Rothblum (2015b). Proofs\nof Proximity for Context-Free Languages and Read-Once Branching\nPrograms - (Extended Abstract). In International Colloquium on Automata,\nLanguages and Programming ICALP. URL https:\/\/doi.org\/10.1007\/978-3-662-47672-7_54.","DOI":"10.1007\/978-3-662-47672-7_54"},{"key":"212_CR29","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Or Sheffet (2010). On The Randomness Complexity\nof Property Testing. Computational Complexity 19(1), 99\u2013133.\nURL https:\/\/doi.org\/10.1007\/s00037-009-0282-4.","DOI":"10.1007\/s00037-009-0282-4"},{"key":"212_CR30","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2015). Zero-\nInformation Protocols and Unambiguity in Arthur-Merlin Communication.\nIn Proceedings of the 2015 Conference on Innovations in Theoretical\nComputer Science, ITCS 2015, Rehovot, Israel, January 11-\n13, 2015, 113\u2013122. URL http:\/\/doi.acm.org\/10.1145\/2688073.2688074.","DOI":"10.1145\/2688073.2688074"},{"key":"212_CR31","doi-asserted-by":"crossref","unstructured":"Tom Gur (2017). On Locally Verifiable Proofs of Proximity. Ph.D.\nthesis, Weizmann Institute.","DOI":"10.31237\/osf.io\/fq3rn"},{"key":"212_CR32","doi-asserted-by":"crossref","unstructured":"Tom Gur & Ran Raz (2015). Arthur-Merlin streaming complexity.\nInf. Comput. 243, 145\u2013165. URL https:\/\/doi.org\/10.1016\/j.ic.2014.12.011.","DOI":"10.1016\/j.ic.2014.12.011"},{"key":"212_CR33","doi-asserted-by":"crossref","unstructured":"Tom Gur & Ron D. Rothblum (2016). Non-interactive proofs of\nproximity. Computational Complexity ISSN 1420-8954. URL https:\/\/doi.org\/10.1007\/s00037-016-0136-9.","DOI":"10.1007\/s00037-016-0136-9"},{"key":"212_CR34","unstructured":"Tom Gur & Ron D. Rothblum (2017). A Hierarchy Theorem for\nInteractive Proofs of Proximity. In Innovations in Theoretical Computer\nScience ITCS."},{"key":"212_CR35","doi-asserted-by":"crossref","unstructured":"Tom Gur & Ron D. Rothblum (2018). Non-interactive proofs of\nproximity. Computational Complexity 27(1), 99\u2013207.","DOI":"10.1007\/s00037-016-0136-9"},{"key":"212_CR36","doi-asserted-by":"crossref","unstructured":"Yael Tauman Kalai & Ron D. Rothblum (2015). Arguments of\nProximity - [Extended Abstract]. In CRYPTO. URL https:\/\/doi.org\/10.1007\/978-3-662-48000-7_21.","DOI":"10.1007\/978-3-662-48000-7_21"},{"key":"212_CR37","doi-asserted-by":"crossref","unstructured":"Bala Kalyanasundaram & Georg Schnitger (1992). The Probabilistic\nCommunication Complexity of Set Intersection. SIAM J. Discrete\nMath. 5(4), 545\u2013557. URL https:\/\/doi.org\/10.1137\/0405044.","DOI":"10.1137\/0405044"},{"key":"212_CR38","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2003). Rectangle Size Bounds and Threshold\nCovers in Communication Complexity. In 18th Annual IEEE Conference\non Computational Complexity (Complexity 2003), 7-10 July 2003,\nAarhus, Denmark, 118\u2013134. URL https:\/\/doi.org\/10.1109\/CCC.2003.1214415.","DOI":"10.1109\/CCC.2003.1214415"},{"key":"212_CR39","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2011). On Arthur Merlin Games in Communication\nComplexity. In Proceedings of the 26th Annual IEEE Conference\non Computational Complexity, CCC 2011, San Jose, California, June\n8-10, 2011, 189\u2013199. URL https:\/\/doi.org\/10.1109\/CCC.2011.33.","DOI":"10.1109\/CCC.2011.33"},{"key":"212_CR40","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity.\nCambridge University Press. ISBN 978-0-521-56067-2.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"212_CR41","doi-asserted-by":"crossref","unstructured":"Carsten Lund, Lance Fortnow, Howard J. Karloff & Noam\nNisan (1992). Algebraic Methods for Interactive Proof Systems. J.\nACM 39(4), 859\u2013868. URL http:\/\/doi.acm.org\/10.1145\/146585.146605.","DOI":"10.1145\/146585.146605"},{"key":"212_CR42","doi-asserted-by":"crossref","unstructured":"Ilan Newman (1991). Private vs. Common Random Bits in Communication\nComplexity. Inf. Process. Lett. 39(2), 67\u201371. URL https:\/\/doi.org\/10.1016\/0020-0190(91)90157-D.","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"212_CR43","doi-asserted-by":"crossref","unstructured":"Ran Raz (2009). Quantum Information and the PCP Theorem.\nAlgorithmica 55(3), 462\u2013489. URL https:\/\/doi.org\/10.1007\/s00453-007-9033-6.","DOI":"10.1007\/s00453-007-9033-6"},{"key":"212_CR44","doi-asserted-by":"crossref","unstructured":"Ran Raz & Amir Shpilka (2004). On the Power of Quantum Proofs.\nIn 19th Annual IEEE Conference on Computational Complexity (CCC\n2004), 21-24 June 2004, Amherst, MA, USA, 260\u2013274. URL https:\/\/doi.org\/10.1109\/CCC.2004.1313849.","DOI":"10.1109\/CCC.2004.1313849"},{"key":"212_CR45","doi-asserted-by":"crossref","unstructured":"Ran Raz, G\u00e1bor Tardos, Oleg Verbitsky & Nikolai K.\nVereshchagin (1998). Arthur-Merlin Games in Boolean Decision\nTrees. In Proceedings of the 13th Annual IEEE Conference on Computational\nComplexity, Buffalo, New York, USA, June 15-18, 1998, 58\u201367.\nURL https:\/\/doi.org\/10.1109\/CCC.1998.694591.","DOI":"10.1109\/CCC.1998.694591"},{"key":"212_CR46","doi-asserted-by":"crossref","unstructured":"Omer Reingold, Guy N. Rothblum & Ron D. Rothblum (2016).\nConstant-round interactive proofs for delegating computation. In Proceedings\nof the 48th Annual ACM SIGACT Symposium on Theory of\nComputing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 49\u201362. URL http:\/\/doi.acm.org\/10.1145\/2897518.2897652.","DOI":"10.1145\/2897518.2897652"},{"key":"212_CR47","doi-asserted-by":"crossref","unstructured":"Dana Ron (2008). Property Testing: A Learning Theory Perspective.\nFoundations and Trends in Machine Learning 1(3), 307\u2013402. URL\nhttps:\/\/doi.org\/10.1561\/2200000004.","DOI":"10.1561\/2200000004"},{"key":"212_CR48","doi-asserted-by":"crossref","unstructured":"Dana Ron (2009). Algorithmic and Analysis Techniques in Property\nTesting. Foundations and Trends in Theoretical Computer Science 5(2),\n73\u2013205. URL https:\/\/doi.org\/10.1561\/0400000029.","DOI":"10.1561\/0400000029"},{"key":"212_CR49","doi-asserted-by":"crossref","unstructured":"Guy N. Rothblum, Salil P. Vadhan & Avi Wigderson (2013).\nInteractive proofs of proximity: delegating computation in sublinear\ntime. In Symposium on Theory of Computing, STOC. URL http:\/\/doi.acm.org\/10.1145\/2488608.2488709.","DOI":"10.1145\/2488608.2488709"},{"key":"212_CR50","doi-asserted-by":"crossref","unstructured":"Ronitt Rubinfeld & Madhu Sudan (1996). Robust Characterizations\nof Polynomials with Applications to Program Testing.\nSIAM J. Comput. 25(2), 252\u2013271. URL https:\/\/doi.org\/10.1137\/S0097539793255151.","DOI":"10.1137\/S0097539793255151"},{"key":"212_CR51","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov (2016). The Multiparty Communication\nComplexity of Set Disjointness. SIAM J. Comput. 45(4), 1450\u20131489.\nURL https:\/\/doi.org\/10.1137\/120891587.","DOI":"10.1137\/120891587"},{"key":"212_CR52","unstructured":"Justin Thaler (2016). Semi-Streaming Algorithms for Annotated\nGraph Streams. In 43rd International Colloquium on Automata, Languages,\nand Programming, ICALP 2016, July 11-15, 2016, Rome, Italy,\n59:1\u201359:14. URL https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.59."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-021-00212-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-021-00212-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-021-00212-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T03:04:33Z","timestamp":1638414273000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-021-00212-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,18]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["212"],"URL":"https:\/\/doi.org\/10.1007\/s00037-021-00212-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,18]]},"assertion":[{"value":"10 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}