{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T13:52:05Z","timestamp":1765806725462},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,10,25]],"date-time":"2008-10-25T00:00:00Z","timestamp":1224892800000},"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":[[2010,12]]},"DOI":"10.1007\/s00453-008-9237-4","type":"journal-article","created":{"date-parts":[[2008,10,24]],"date-time":"2008-10-24T14:54:41Z","timestamp":1224860081000},"page":"811-830","source":"Crossref","is-referenced-by-count":7,"title":["On the Benefits of Adaptivity in Property Testing of\u00a0Dense Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Mira","family":"Gonen","sequence":"first","affiliation":[]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,10,25]]},"reference":[{"key":"9237_CR1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.10056","volume":"21","author":"N. Alon","year":"2002","unstructured":"Alon, N.: Testing subgraphs of large graphs. Random Struct. Algorithms 21, 359\u2013370 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"9237_CR2","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, 451\u2013476 (2000)","journal-title":"Combinatorica"},{"key":"9237_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: It\u2019s all about regularity. In: Proc. 38th Symposium on the Theory of Computing (STOC) (2006)","DOI":"10.1145\/1132516.1132555"},{"key":"9237_CR4","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1137\/S0895480199358655","volume":"15","author":"N. Alon","year":"2002","unstructured":"Alon, N., Krivelevich, M.: Testing k-colorability. SIAM J. Discrete Math. 15, 211\u2013227 (2002)","journal-title":"SIAM J. Discrete Math."},{"key":"9237_CR5","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1017\/S0963548306007759","volume":"15","author":"N. Alon","year":"2005","unstructured":"Alon, N., Shapira, A.: A characterization of easily testable induced subgraphs. Comb. Probab. Comput. 15, 791\u2013805 (2005)","journal-title":"Comb. Probab. Comput."},{"key":"9237_CR6","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: Every monotone graph property is testable. In: Proc. 37th Symposium on the Theory of Computing (STOC), pp.\u00a0129\u2013137 (2005). To appear in SICOMP","DOI":"10.1145\/1060590.1060611"},{"key":"9237_CR7","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (2000)"},{"issue":"1","key":"9237_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: 3CNF properties are hard to test. SIAM J. Comput. 35(1), 1\u201321 (2005)","journal-title":"SIAM J. Comput."},{"key":"9237_CR9","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: Lower bounds for testing bipartiteness in dense graphs. In: Proc. 19th IEEE Symp. Computational Complexity Conference, pp. 75\u201381 (2004)","DOI":"10.1109\/CCC.2004.1313803"},{"issue":"3","key":"9237_CR10","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1137\/S009753970444199X","volume":"34","author":"A. Czumaj","year":"2005","unstructured":"Czumaj, A., Sohler, C.: Abstract combinatorial programs and efficient property testers. SIAM J. Comput. 34(3), 580\u2013615 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9237_CR11","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Ergun","year":"2000","unstructured":"Ergun, F., Kannan, S., Kumar, S.R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J. Comput. Syst. Sci. 60(3), 717\u2013751 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9237_CR12","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Bull. Eur. Assoc. Theor. Comput. Sci. 75, 97\u2013126 (2001)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"9237_CR13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.ic.2003.09.003","volume":"189","author":"E. Fischer","year":"2004","unstructured":"Fischer, E.: On the strength of comparisons in property testing. Inf. Comput. 189, 107\u2013116 (2004)","journal-title":"Inf. Comput."},{"issue":"3","key":"9237_CR14","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.20037","volume":"26","author":"E. Fischer","year":"2005","unstructured":"Fischer, E.: Testing graphs for colorability properties. Random Struct. Algorithms 26(3), 289\u2013309 (2005)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9237_CR15","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1137\/060652324","volume":"37","author":"E. Fischer","year":"2007","unstructured":"Fischer, E., Newman, I.: Testing versus estimation of graph properties. SIAM J. Comput. 37(2), 482\u2013501 (2007)","journal-title":"SIAM J. Comput."},{"key":"9237_CR16","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorial property testing\u2014a survey. In: Randomization Methods in Algorithm Design, pp.\u00a045\u201360 (1998)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"9237_CR17","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 connections to learning and approximation. J. ACM 45, 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"9237_CR18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartite tester for bounded degree graphs. Combinatorica 19(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"9237_CR19","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)","journal-title":"Algorithmica"},{"issue":"1","key":"9237_CR20","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)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9237_CR21","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/rsa.3240010209","volume":"1","author":"S. Janson","year":"1990","unstructured":"Janson, S.: Poisson approximation for large deviations. Random Struct. Algorithms 1(2), 221\u2013229 (1990)","journal-title":"Random Struct. Algorithms"},{"issue":"6","key":"9237_CR22","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)","journal-title":"SIAM J. Comput."},{"key":"9237_CR23","unstructured":"Raskhodnikova, S., Smith, A.: A note on adaptivity in testing properties of bounded degree graphs. Technical Report TR06-089, Electronic Colloquium on Computational Complexity (ECCC) (2006). Available from http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"9237_CR24","doi-asserted-by":"crossref","unstructured":"Ron, D.: Property testing. In: Handbook on Randomization, vol. II, pp.\u00a0597\u2013649 (2001)","DOI":"10.1007\/978-1-4615-0013-1_15"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9237-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9237-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9237-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T17:49:04Z","timestamp":1684604944000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9237-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,25]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["9237"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9237-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,25]]}}}