{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:00Z","timestamp":1725490200944},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_38","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T10:52:26Z","timestamp":1188211946000},"page":"525-539","source":"Crossref","is-referenced-by-count":8,"title":["On the Benefits of Adaptivity in Property Testing of Dense Graphs"],"prefix":"10.1007","author":[{"given":"Mira","family":"Gonen","sequence":"first","affiliation":[]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","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\u00a020, 451\u2013476 (2000)","journal-title":"Combinatorica"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/S0895480199358655","volume":"15","author":"N. Alon","year":"2002","unstructured":"Alon, N., Krivelevich, M.: Testing k-colorability. SIAM J. on Discrete Mathematics\u00a015, 211\u2013227 (2002)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"38_CR3","doi-asserted-by":"publisher","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)"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: 3CNF properties are hard to test. In: Proc. 35th Symposium on the Theory of Computing (STOC), pp. 345\u2013354 (2003)","DOI":"10.1145\/780591.780594"},{"key":"38_CR5","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":"38_CR6","doi-asserted-by":"publisher","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. Journal of Computer and Systems Science\u00a060(3), 717\u2013751 (2000)","journal-title":"Journal of Computer and Systems Science"},{"key":"38_CR7","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"38_CR8","doi-asserted-by":"publisher","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. Information and Computation\u00a0189, 107\u2013116 (2004)","journal-title":"Information and Computation"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorial property testing - a survey. Randomization Methods in Algorithm Design, pp. 45\u201360 (1998)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"38_CR10","doi-asserted-by":"publisher","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. Journal of the ACM\u00a045, 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"issue":"3","key":"38_CR11","doi-asserted-by":"publisher","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\u00a019(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica, 302\u2013343 (2002)","DOI":"10.1007\/s00453-001-0078-7"},{"issue":"1","key":"38_CR13","doi-asserted-by":"publisher","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 Structures and Algorithms\u00a023(1), 23\u201357 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"Gonen, M., Ron, D.: On the benefits of adaptivity in property testing of dense graphs (2007), available from http:\/\/www.eng.tau.ac.il\/~danar","DOI":"10.1007\/978-3-540-74208-1_38"},{"issue":"2","key":"38_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/rsa.3240010209","volume":"1","author":"S. Janson","year":"1990","unstructured":"Janson, S.: Poisson approximaton for large deviations. Random Structures and Algorithms\u00a01(2), 221\u2013229 (1990)","journal-title":"Random Structures and Algorithms"},{"issue":"6","key":"38_CR16","doi-asserted-by":"publisher","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 Journal on Computing\u00a033(6), 1441\u20131483 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR17","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":"38_CR18","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","volume":"II","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing. In Handbook on Randomization\u00a0II, 597\u2013649 (2001)","journal-title":"In Handbook on Randomization"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T12:29:47Z","timestamp":1556800187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":18,"URL":"http:\/\/dx.doi.org\/10.1007\/978-3-540-74208-1_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}
