{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T22:39:28Z","timestamp":1718923168983},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,9]],"date-time":"2007-10-09T00:00:00Z","timestamp":1191888000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00453-007-9054-1","type":"journal-article","created":{"date-parts":[[2007,10,8]],"date-time":"2007-10-08T16:35:10Z","timestamp":1191861310000},"page":"24-48","source":"Crossref","is-referenced-by-count":1,"title":["Distribution-Free Connectivity Testing for Sparse Graphs"],"prefix":"10.1007","volume":"51","author":[{"given":"Shirley","family":"Halevy","sequence":"first","affiliation":[]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,9]]},"reference":[{"issue":"2","key":"9054_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0196-6774(03)00019-1","volume":"47","author":"N. Alon","year":"2003","unstructured":"Alon, N., Shapira, A.: Testing satisfiability. J. Algorithms 47(2), 87\u2013103 (2003) (also appeared in SODA, pp.\u00a0645\u2013654, 2002)","journal-title":"J. Algorithms"},{"issue":"3","key":"9054_CR2","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/j.jcss.2004.04.008","volume":"69","author":"N. Alon","year":"2004","unstructured":"Alon, N., Shapira, A.: Testing subgraphs in directed graphs. J. Comput. Syst. Sci. 69(3), 354\u2013382 (2004) (also appeared in STOC, pp.\u00a0700\u2013709, 2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9054_CR3","unstructured":"Alon, N., Shapira, A.: A characterization of easily testable induced subgraphs. SODA, pp. 942\u2013951 (2004)"},{"key":"9054_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. FOCS, pp. 429\u2013438 (2005)","DOI":"10.1109\/SFCS.2005.5"},{"key":"9054_CR5","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: Every monotone graph property is testable. STOC, pp. 128\u2013137 (2005)","DOI":"10.1145\/1060590.1060611"},{"issue":"4","key":"9054_CR6","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s004930070001","volume":"20","author":"N. Alon","year":"2000","unstructured":"Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs. Combinatorica 20(4), 451\u2013476 (2000) (also appeared in FOCS, pp.\u00a0656\u2013666, 1999)","journal-title":"Combinatorica"},{"key":"9054_CR7","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1137\/S0097539700366528","volume":"30","author":"N. Alon","year":"2001","unstructured":"Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. SIAM J. Comput. 30, 1842\u20131862 (2001) (also appeared in FOCS, pp.\u00a0645\u2013655, 1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9054_CR8","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1137\/S0895480102410973","volume":"16","author":"N. Alon","year":"2003","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of clustering. SIAM J. Discrete Math. 16(3), 393\u2013417 (2003) (also appeared in FOCS, pp.\u00a0240\u2013251, 2001)","journal-title":"SIAM J. Discrete Math."},{"key":"9054_CR9","doi-asserted-by":"crossref","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing low-degree polynomials over GF(2). RANDOM-APPROX, pp. 188\u2013199 (2003)","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"9054_CR10","doi-asserted-by":"crossref","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Ron, D.: Testing triangle-freeness in general graphs. SODA, pp.\u00a0279\u2013288 (2006)","DOI":"10.1145\/1109557.1109589"},{"issue":"3","key":"9054_CR11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica 23(3), 365\u2013426 (2003) (also appeared in STOC, pp.\u00a0485\u2013495, 1997)","journal-title":"Combinatorica"},{"issue":"1","key":"9054_CR12","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.ic.2004.10.001","volume":"196","author":"T. Batu","year":"2005","unstructured":"Batu, T., Rubinfeld, R., White, P.: Fast approximation PCPs for multidimensional bin-packing problems. Inf. Comput. 196(1), 42\u201356 (2005) (also appeared in RANDOM-APPROX, pp.\u00a0246\u2013256, 1999)","journal-title":"Inf. Comput."},{"key":"9054_CR13","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"9054_CR14","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. FOCS, pp. 93\u2013102 (2002)","DOI":"10.1109\/SFCS.2002.1181886"},{"issue":"1","key":"9054_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2004.09.031","volume":"331","author":"A. Czumaj","year":"2005","unstructured":"Czumaj, A., Sohler, C.: Testing hypergraph colorability. Theor. Comput. Sci. 331(1), 37\u201352 (2005) (also appeared in ICALP, pp.\u00a0493\u2013505, 2001)","journal-title":"Theor. Comput. Sci."},{"key":"9054_CR16","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. RANDOM-APPROX, pp. 97\u2013108 (1999)","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"9054_CR17","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Erg\u00fcn","year":"2000","unstructured":"Erg\u00fcn, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J. Comput. Syst. Sci. 60, 717\u2013751 (2000) (a preliminary version appeared in STOC, 1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9054_CR18","unstructured":"Fischer, E.: On the strength of comparisons in property testing. Manuscript, available at ECCC TR00-083"},{"key":"9054_CR19","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: a primer to property testing. Comput. Complex. Column Bull. Eur. Assoc. Theor. Comput. Sci. 75, 97\u2013126 (2001)","journal-title":"Comput. Complex. Column Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"9054_CR20","doi-asserted-by":"crossref","unstructured":"Fischer, E., Newman, I.: Testing of matrix properties. STOC, pp. 286\u2013295 (2001)","DOI":"10.1145\/380752.380812"},{"key":"9054_CR21","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. STOC, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"4","key":"9054_CR22","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"E. Fischer","year":"2004","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. J. Comput. Syst. Sci. 68(4), 753\u2013787 (2004) (also appeared in FOCS, pp.\u00a0103\u2013112, 2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9054_CR23","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"P. Gemmell","year":"1993","unstructured":"Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self testing\/correcting for polynomials and for approximate functions. J. Comput. Syst. Sci. 47(3), 549\u2013595 (1993) (also appeared in STOC, pp.\u00a032\u201342, 1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9054_CR24","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorical property testing\u2014a survey. In: Pardalos, P., Rajasekaran, S., Rolim, J. (eds.) Randomized Methods in Algorithms Design. AMS-DIMACS, pp. 45\u201361 (1998)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"9054_CR25","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Electron. Colloq. Comput. Complex. 7(20) (2000)"},{"issue":"2","key":"9054_CR26","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302\u2013343 (2002) (also appeared in STOC, pp.\u00a0406\u2013415, 1997)","journal-title":"Algorithmica"},{"issue":"1","key":"9054_CR27","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/rsa.10078","volume":"23","author":"O. Goldreich","year":"2003","unstructured":"Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Struct. Algorithms 23(1), 23\u201357 (2003) (also appeared in FOCS, pp.\u00a0302\u2013317, 2001)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"9054_CR28","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM 45(4), 653\u2013750 (1998) (a preliminary version appeared in FOCS, 1996)","journal-title":"JACM"},{"issue":"3","key":"9054_CR29","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301\u2013337 (2000) (a preliminary version appeared in FOCS, 1998)","journal-title":"Combinatorica"},{"key":"9054_CR30","doi-asserted-by":"crossref","unstructured":"Halevy, S., Kushilevitz, E.: Distribution free property testing. RANDOM-APPROX, pp. 341\u2013353 (2003)","DOI":"10.1007\/978-3-540-45198-3_26"},{"key":"9054_CR31","doi-asserted-by":"crossref","unstructured":"Halevy, S., Kushilevitz, E.: Testing monotonicity over graph products. ICALP, pp. 721\u2013732 (2004)","DOI":"10.1007\/978-3-540-27836-8_61"},{"issue":"6","key":"9054_CR32","doi-asserted-by":"crossref","first-page":"1441","DOI":"10.1137\/S0097539703436424","volume":"33","author":"T. Kaufman","year":"2004","unstructured":"Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput. 33(6), 1441\u20131483 (2004) (also appeared in RANDOM-APPROX, pp.\u00a0341\u2013353, 2003)","journal-title":"SIAM J. Comput."},{"key":"9054_CR33","doi-asserted-by":"crossref","unstructured":"Kohayakawa, Y., Nagle, B., Rodl, V.: Efficient testing of hypergraphs. ICALP, pp. 1017\u20131028 (2002)","DOI":"10.1007\/3-540-45465-9_87"},{"issue":"5","key":"9054_CR34","doi-asserted-by":"crossref","first-page":"1557","DOI":"10.1137\/S009753970038211X","volume":"31","author":"I. Newman","year":"2002","unstructured":"Newman, I.: Testing of functions that have small width branching programs. SIAM J. Comput. 31(5), 1557\u20131570 (2002) (also appeared in FOCS, pp.\u00a0251\u2013258, 2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9054_CR35","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D.: Testing the diameter of graphs. Random Struct. Algorithms 20(2), 165\u2013183 (2002) (also appeared in RANDOM-APPROX, pp.\u00a085\u201396, 1999)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9054_CR36","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0890-5401(03)00160-3","volume":"187","author":"M. Parnas","year":"2003","unstructured":"Parnas, M., Ron, D.: Testing metric properties. Inf. Comput. 187(2), 155\u2013195 (2003) (also appeared in STOC, pp.\u00a0276\u2013285, 2001)","journal-title":"Inf. Comput."},{"key":"9054_CR37","doi-asserted-by":"crossref","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Proclaiming dictators and juntas or testing boolean formulae. RANDOM-APPROX, pp. 273\u2013284 (2001)","DOI":"10.1007\/3-540-44666-4_30"},{"issue":"1","key":"9054_CR38","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1002\/rsa.10067","volume":"22","author":"M. Parnas","year":"2003","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Testing membership in parenthesis languages. Random Struct. Algorithms 22(1), 98\u2013138 (2003) (also appeared in RANDOM-APPROX, pp.\u00a0261\u2013272, 2001)","journal-title":"Random Struct. Algorithms"},{"key":"9054_CR39","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolin, J.D.P. (eds.) Handbook of Randomized Computing. Kluwer Academic, Dordrecht (2001)"},{"issue":"6","key":"9054_CR40","doi-asserted-by":"crossref","first-page":"1972","DOI":"10.1137\/S0097539796298625","volume":"28","author":"R. Rubinfeld","year":"1999","unstructured":"Rubinfeld, R.: Robust functional equations and their applications to program testing. SIAM J. Comput. 28(6), 1972\u20131997 (1999) (appeared in FOCS, 1994)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9054_CR41","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996) (first appeared as a technical report, Cornell University, 1993)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9054-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9054-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9054-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9054-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,9]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9054"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9054-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,9]]}}}