{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T23:23:43Z","timestamp":1791069823608,"version":"4.1.0"},"reference-count":119,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the types of answers that one can hope to achieve in this setting.<\/jats:p>","DOI":"10.1137\/100791075","type":"journal-article","created":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T18:06:45Z","timestamp":1321985205000},"page":"1562-1588","source":"Crossref","is-referenced-by-count":53,"title":["Sublinear Time Algorithms"],"prefix":"10.1137","volume":"25","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,11,22]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20167"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Alon,\n                      On constant time approximation of parameters of bounded degree graphs\n                      , in Property Testing\u2014Current Research and Surveys, O. Goldreich, ed., Lecture Notes in Comput. Sci. 6390, Springer, New York, 2010, pp. 234\u2013239.","DOI":"10.1007\/978-3-642-16367-8_14"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"N. Alon, T. Kaufman, M. Krivilevich, S. Litsyn, and D. Ron,\n                      Testing low-degree polynomials over gf(2)\n                      , in Proceedings of RANDOM '03, Princeton, NJ, Lecture Notes in Comput. Sci. 2764, Springer, New York, 2003, pp. 188\u2013199.","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/07067917X"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199358655"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Seymour, and R. Thomas,\n                      A separator theorem for graphs with an excluded minor and its applications\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, 1990, pp. 293\u2013299.","DOI":"10.1145\/100216.100254"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.008"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Andoni, R. Krauthgamer, and K. Onak,\n                      Polylogarithmic approximation for edit distance and the asymmetric query complexity\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 2010, pp. 377\u2013386.","DOI":"10.1109\/FOCS.2010.43"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. Arora and M. Sudan,\n                      Improved low degree testing and its applications\n                      , in Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, TX, 1997, pp. 485\u2013495.","DOI":"10.1145\/258533.258642"},{"key":"R19","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1002\/rsa.20300","volume":"36","author":"Austin T.","year":"2010","journal-title":"Random Struct. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1042-9832","issn-type":"print"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy,\n                      Checking computations in polylogarithmic time\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, 1991, pp. 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.006"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"T. Batu, F. Ergun, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami,\n                      A sublinear algorithm for weakly approximating edit distance\n                      , in Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, San Diego, 2003, pp. 316\u2013324.","DOI":"10.1145\/780542.780590"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.10.001"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"R25","unstructured":"I. Ben-Eliezer, T. Kaufman, M. Krivelevich, and D. Ron,\n                      Comparing the strength of query types in property testing: The case of testing k-colorability\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 2008, pp. 1213\u20131222."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20182"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"I. Benjamini, O. Schramm, and A. Shapira,\n                      Every minor-closed property of sparse graphs is testable\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, BC, 2008, pp. 393\u2013402.","DOI":"10.1145\/1374376.1374433"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a006"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. P. Woodruff,\n                      Transitive-closure spanners\n                      , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, 2009, pp. 932\u2013941.","DOI":"10.1137\/1.9781611973068.101"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya and N. Xie,\n                      Lower bounds for testing triangle-freeness in Boolean functions\n                      , in Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, 2010, pp. 87\u201398.","DOI":"10.1137\/1.9781611973075.9"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"A. Bogdanov, K. Obata, and L. Trevisan,\n                      A lower bound for testing 3-colorability in bounded-degree graphs\n                      , in Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, Vancouver, BC, 2002, pp. 93\u2013102.","DOI":"10.1109\/SFCS.2002.1181886"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70495-3"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018585"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"E. Ben Sasson, M. Sudan, S. Vadhan, and A. Wigderson,\n                      Randomness-efficient low degree tests and short PCP's via epsilon-biased sets\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, 2003, pp. 612\u2013621.","DOI":"10.1145\/780542.780631"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444572X"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"R39","unstructured":"D. Coppersmith,\n                      handwritten notes\n                      , 1989."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435297"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"A. Czumaj and C. Sohler,\n                      Testing expansion in bounded-degree graphs\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 2007, pp. 570\u2013578.","DOI":"10.1109\/FOCS.2007.33"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/060672121"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/070681831"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky,\n                      Improved testing algorithms for monotonicity\n                      , in Proceedings of RANDOM 1999, Lecture Notes in Comput. Sci. 1671, Springer, New York, 1999, pp. 97\u2013108.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"R46","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1002\/rsa.20308","volume":"37","author":"Elek G.","year":"2010","journal-title":"Random Structures Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1042-9832","issn-type":"print"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300003260"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337613"},{"key":"R50","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky,\n                      Monotonicity testing over general poset domains\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montr\u00e9al, QC, 2002, pp. 474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"G. Frahling, P. Indyk, and C. Sohler,\n                      Sampling in dynamic data streams and applications\n                      , in Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, 2005, pp. 142\u2013149.","DOI":"10.1145\/1064092.1064116"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"E. Fischer and A. Matsliah,\n                      Testing graph isomorphism\n                      , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, 2006, pp. 299\u2013308.","DOI":"10.1145\/1109557.1109591"},{"key":"R56","doi-asserted-by":"crossref","unstructured":"E. Fischer, A. Matsliah, and A. Shapira,\n                      Approximate hypergraph partitioning and applications\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 2007, pp. 579\u2013589.","DOI":"10.1109\/FOCS.2007.12"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1137\/060652324"},{"key":"R58","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R59","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Combinatorial property testing\u2014A survey\n                      , in Randomization Methods in Algorithm Design, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, 1998, pp. 45\u201360.","DOI":"10.1090\/dimacs\/043\/04"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R62","doi-asserted-by":"crossref","unstructured":"O. Goldreich, M. Krivelevich, I. Newman, and E. Rozenberg,\n                      Hierarchy theorems for property testing\n                      , in Proceedings of RANDOM 2009, Berkeley, CA, pp. 504\u2013519.","DOI":"10.1007\/978-3-642-03685-9_38"},{"key":"R63","unstructured":"O. Goldreich and D. Ron,\n                      On testing expansion in bounded-degree graphs\n                      , Electron. Colloq. Comput. Complexity, 7 (2000)."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"R65","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"R67","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Trevisan,\n                      Three theorems regarding testing graph properties\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 2001, pp. 460\u2013469.","DOI":"10.1109\/SFCS.2001.959922"},{"key":"R68","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"R69","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0509-8"},{"key":"R70","doi-asserted-by":"crossref","unstructured":"S. Halevy and E. Kushilevitz,\n                      Testing monotonicity over graph products\n                      , in Proceedings of ICALP, Lecture Notes in Comput. Sci. 3142, Springer, New York, 2004, pp. 721\u2013732.","DOI":"10.1007\/978-3-540-27836-8_61"},{"key":"R71","doi-asserted-by":"crossref","unstructured":"A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak,\n                      Local graph partitions for approximation and testing\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, 2009, pp. 22\u201331.","DOI":"10.1109\/FOCS.2009.77"},{"key":"R72","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"R73","doi-asserted-by":"crossref","unstructured":"P. Indyk,\n                      Sublinear time algorithms for metric space problems\n                      , in Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, GA, 1999, pp. 428\u2013434.","DOI":"10.1145\/301250.301366"},{"key":"R74","doi-asserted-by":"crossref","unstructured":"C. S. Jutla, A. C. Patthak, A. Rudra, and D. Zuckerman,\n                      Testing low-degree polynomials over prime fields\n                      , in Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science, Rome, 2004, pp. 423\u2013432.","DOI":"10.1109\/FOCS.2004.64"},{"key":"R75","doi-asserted-by":"crossref","unstructured":"S. Kale and C. Seshadhri,\n                      An expansion tester for bounded-degree graphs\n                      , in Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, Reykjavik, Iceland, 2008, pp. 527\u2013538.","DOI":"10.1007\/978-3-540-70575-8_43"},{"key":"R76","doi-asserted-by":"crossref","unstructured":"T. Kaufman and S. Litsyn,\n                      Almost orthogonal linear codes are locally testable\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 2005, pp. 317\u2013326.","DOI":"10.1109\/SFCS.2005.16"},{"key":"R77","doi-asserted-by":"publisher","DOI":"10.1137\/080715548"},{"key":"R78","doi-asserted-by":"crossref","unstructured":"T. Kaufman and D. Ron,\n                      Testing polynomials over general fields\n                      , in Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science, Rome, 2004, pp. 413\u2013422.","DOI":"10.1109\/FOCS.2004.65"},{"key":"R79","doi-asserted-by":"crossref","unstructured":"T. Kaufman and M. Sudan,\n                      Sparse random linear codes are locally decodable and testable\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 2007, pp. 590\u2013600.","DOI":"10.1109\/FOCS.2007.8"},{"key":"R80","doi-asserted-by":"crossref","unstructured":"T. Kaufman and M. Sudan,\n                      Algebraic property testing: The role of invariance\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, BC, 2008, pp. 403\u2013412.","DOI":"10.1145\/1374376.1374434"},{"key":"R81","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00004-7"},{"key":"R82","first-page":"8109","volume":"102","author":"Kohayakawa Y.","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA","ISSN":"https:\/\/id.crossref.org\/issn\/0027-8424","issn-type":"print"},{"key":"R83","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215920"},{"key":"R84","doi-asserted-by":"crossref","unstructured":"S. Kopparty and S. Saraf,\n                      Tolerant linearity testing and locally testable codes\n                      , in APPROX-RANDOM 2009, Berkeley, CA, Lecture Notes in Comput. Sci. 5687, Springer, New York, 2009, pp. 601\u2013614.","DOI":"10.1007\/978-3-642-03685-9_45"},{"key":"R85","doi-asserted-by":"crossref","unstructured":"S. Kopparty and S. Saraf,\n                      Local list-decoding and testing of sparse random linear codes from high-error\n                      , in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, Cambridge, MA, 2010, pp. 417\u2013426.","DOI":"10.1145\/1806689.1806748"},{"key":"R86","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"R87","doi-asserted-by":"crossref","unstructured":"F. Kuhn, T. Moscibroda, and R. Wattenhofer,\n                      The price of being near-sighted\n                      , in Proceedings of the Seventeenth Annual ACM\/SIAM Symposium on Discrete Algorithms, Miami, FL, 2006, pp. 980\u2013989.","DOI":"10.1145\/1109557.1109666"},{"key":"R88","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.12.003"},{"key":"R89","unstructured":"D. Kr\u00e1l', O. Serra, and L. Vena,\n                      A removal lemma for linear systems over finite fields\n                      , Proc. VI J. Mat. Discreta Algor\u00edtmica, 2008, pp. 417\u2013424."},{"key":"R90","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"R91","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"R92","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"R93","doi-asserted-by":"crossref","unstructured":"S. Marko and D. Ron,\n                      Approximating the distance to properties in bounded-degree and general sparse graphs\n                      , ACM Trans. Algorithms, 5 (2009), 22.","DOI":"10.1145\/1497290.1497298"},{"key":"R94","doi-asserted-by":"publisher","DOI":"10.1137\/080729967"},{"key":"R95","unstructured":"N. Mishra, D. Oblinger, and L. Pitt,\n                      Sublinear time approximate clustering\n                      , in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, 2001, pp. 439\u2013447."},{"key":"R96","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.09.002"},{"key":"R97","doi-asserted-by":"crossref","unstructured":"H. N. Nguyen and K. Onak,\n                      Constant-time approximation algorithms via local improvements\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 2008, pp. 327\u2013336.","DOI":"10.1109\/FOCS.2008.81"},{"key":"R98","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013"},{"key":"R99","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"R100","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"R101","doi-asserted-by":"crossref","unstructured":"A. Polischuk and D. Spielman,\n                      Nearly linear-size holographic proofs\n                      , in Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, Montr\u00e9al, QC, 1994, pp. 194\u2013203.","DOI":"10.1145\/195058.195132"},{"key":"R102","doi-asserted-by":"crossref","unstructured":"S. Raskhodnikova, D. Ron, R. Rubinfeld, and A. Smith,\n                      Sublinear algorithms for string compressibility and the distribution support size\n                      , in Proceedings of APPROX-RANDOM, Princeton, NJ, Lecture Notes in Comput. Sci. 4627, Springer, New York, 2007, pp. 609\u2013623.","DOI":"10.1007\/978-3-540-74208-1_44"},{"key":"R103","doi-asserted-by":"crossref","unstructured":"S. Raskhodnikova, D. Ron, A. Shpilka, and A. Smith,\n                      Strong lower bounds for approximating distribution support size and the distinct elements problem\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 2007, pp. 559\u2013569.","DOI":"10.1109\/FOCS.2007.47"},{"key":"R104","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra,\n                      A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP\n                      , in Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, TX, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"R105","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582932"},{"key":"R106","doi-asserted-by":"crossref","unstructured":"V. R\u00f6dl and M. Schacht,\n                      Property testing in hypergraphs and the removal lemma\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2007, pp. 488\u2013495.","DOI":"10.1145\/1250790.1250862"},{"key":"R107","doi-asserted-by":"crossref","unstructured":"D. Ron,\n                      Property testing\n                      , in Handbook on Randomization, Volume II, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001, pp. 597\u2013649.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"R108","doi-asserted-by":"publisher","DOI":"10.1561\/2200000004"},{"key":"R109","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.1.104"},{"key":"R110","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298625"},{"key":"R111","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R112","unstructured":"I. Ruzsa and E. Szemer\u00e9di,\n                      Triple systems with no six points carrying three triangles\n                      , in Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II, North\u2013Holland, Amsterdam, pp. 939\u2013945."},{"key":"R113","doi-asserted-by":"crossref","unstructured":"A. Samorodnitsky and L. Trevisan,\n                      A PCP characterization of NP with optimal amortized query complexity\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 191\u2013199.","DOI":"10.1145\/335305.335329"},{"key":"R114","doi-asserted-by":"crossref","unstructured":"A. Shapira,\n                      Green's conjecture and testing linear-invariant properties\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, MD, 2009, pp. 159\u2013166.","DOI":"10.1145\/1536414.1536438"},{"key":"R115","doi-asserted-by":"crossref","unstructured":"A. Shpilka and A. Wigderson,\n                      Derandomizing homomorphism testing in general groups\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, 2004, pp. 427\u2013435.","DOI":"10.1145\/1007352.1007421"},{"key":"R116","doi-asserted-by":"crossref","unstructured":"M. Sudan,\n                      Invariance in property testing\n                      , in Property Testing: Current Research and Surveys, O. Goldreich, ed., Lecture Notes in Comput. Sci. 6390, Springer, New York, 2010, pp. 211\u2013227.","DOI":"10.1007\/978-3-642-16367-8_12"},{"key":"R117","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Proceedings of the Colloque Inter. CNRS, J. C. Bermond, J. C. Fournier, M. Las Vergnas, and D. Sotteau, eds., CNRS, Paris, 1978, pp. 399\u2013401."},{"key":"R118","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.11.006"},{"key":"R119","doi-asserted-by":"crossref","unstructured":"Y. Yoshida, M. Yamamoto, and H. Ito,\n                      An improved constant-time approximation algorithm for maximum matchings\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, MD, 2009, pp. 225\u2013234.","DOI":"10.1145\/1536414.1536447"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100791075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:25Z","timestamp":1787319865000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100791075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":119,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100791075"],"URL":"https:\/\/doi.org\/10.1137\/100791075","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}