{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T21:31:49Z","timestamp":1676669509126},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,9,21]],"date-time":"2012-09-21T00:00:00Z","timestamp":1348185600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00037-012-0048-2","type":"journal-article","created":{"date-parts":[[2012,9,20]],"date-time":"2012-09-20T08:05:54Z","timestamp":1348128354000},"page":"89-135","source":"Crossref","is-referenced-by-count":3,"title":["Comparing the strength of query types in property testing: The case of k-colorability"],"prefix":"10.1007","volume":"22","author":[{"given":"Ido","family":"Ben-Eliezer","sequence":"first","affiliation":[]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,9,21]]},"reference":[{"key":"48_CR1","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. (2000) Efficient Testing of Large Graphs. Combinatorica 20: 451\u2013476","journal-title":"Combinatorica"},{"key":"48_CR2","unstructured":"N. Alon, E. Fischer, I. Newman & A. Shapira (2007). A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In Proceedings of the 38th ACM STOC, 251\u2013260."},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon, T. Kaufman, M. Krivelevich & D. Ron (2006). Testing triangle freeness in general graphs. In Proceedings of the 17th ACM-SIAM SODA, 279\u2013288.","DOI":"10.1145\/1109557.1109589"},{"issue":"2","key":"48_CR4","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1137\/S0895480199358655","volume":"15","author":"N. Alon","year":"2002","unstructured":"Alon N., Krivelevich M. (2002) Testing k-colorability. SIAM Journal on Discrete Math 15(2): 211\u2013227","journal-title":"SIAM Journal on Discrete Math"},{"key":"48_CR5","unstructured":"N. Alon & J. Spencer (2000). The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York."},{"key":"48_CR6","doi-asserted-by":"crossref","unstructured":"A. Bogdanov, K. Obata & L. Trevisan (2002). A lower bound for testing 3-colorability in bounded degree graphs. In Proceedings of the 43th IEEE FOCS, 93\u2013102.","DOI":"10.1109\/SFCS.2002.1181886"},{"key":"48_CR7","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s (2001). Random Graphs. Cambridge University Press. 2nd edition.","DOI":"10.1017\/CBO9780511814068"},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"A. Czumaj, A. Shapira & C. Sohler (2009). Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs. SIAM Journal on Computing 38(6), 2499\u20132510. This is a journal version of Czumaj Sohler (2007).","DOI":"10.1137\/070681831"},{"key":"48_CR9","unstructured":"A. Czumaj & C. Sohler (2007). On testable properties in bounded degree graphs. In Proceedings of the 18th ACM-SIAM SODA, 494\u2013501."},{"key":"48_CR10","unstructured":"D. Du & F. Hwang (1993). Combinatorial group testing and its applications. World Scientific."},{"key":"48_CR11","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1112\/S0025579300003260","volume":"9","author":"P. Erd\u00f6s","year":"1962","unstructured":"Erd\u00f6s P. (1962) On circuits and subgraphs of chromatic graphs. Mathematika 9: 170\u2013175","journal-title":"Mathematika"},{"issue":"4","key":"48_CR12","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U. Feige","year":"2006","unstructured":"Feige U. (2006) On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. SIAM Journal on Computing 35(4): 964\u2013984","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"48_CR13","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. (1998) Property Testing and its Connection to Learning and Approximation. JACM 45(4): 653\u2013750","journal-title":"JACM"},{"issue":"3","key":"48_CR14","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"Goldreich O., Ron D. (1999) A Sublinear Bipartite Tester for Bounded Degree Graphs. Combinatorica 19(3): 335\u2013373","journal-title":"Combinatorica"},{"issue":"2","key":"48_CR15","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. (2002) Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302\u2013343","journal-title":"Algorithmica"},{"issue":"4","key":"48_CR16","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1002\/rsa.20203","volume":"32","author":"O. Goldreich","year":"2008","unstructured":"Goldreich O., Ron D. (2008) Approximating average parameters of graphs. Random Structures and Algorithms 32(4): 473\u2013493","journal-title":"Random Structures and Algorithms"},{"issue":"6","key":"48_CR17","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. (2004) Tight Bounds for Testing Bipartiteness in General Graphs. SIAM Journal on Computing 33(6): 1441\u20131483","journal-title":"SIAM Journal on Computing"},{"key":"48_CR18","unstructured":"R. Motwani & P. Raghavan (1995). Randomized algorithms. Cambridge University Press."},{"key":"48_CR19","doi-asserted-by":"crossref","first-page":"1292","DOI":"10.1109\/18.850669","volume":"46","author":"E. Ordentlich","year":"2000","unstructured":"Ordentlich E., Roth R.M. (2000) Two-dimensional weight-constrained codes through enumeration bounds. IEEE Trans. Inf. Theory 46: 1292\u20131301","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"48_CR20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"M. Parnas","year":"2002","unstructured":"Parnas M., Ron D. (2002) Testing the Diameter of Graphs. Random Structures and Algorithms 20(2): 165\u2013183","journal-title":"Random Structures and Algorithms"},{"key":"48_CR21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02582932","volume":"1","author":"V. R\u00f6dl","year":"1985","unstructured":"R\u00f6dl V., Duke R.A. (1985) On graphs with small subgraphs of large chromatic number. Graphs Combin 1: 91\u201396","journal-title":"Graphs Combin"},{"issue":"2","key":"48_CR22","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld R., Sudan M. (1996) Robust Characterization of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2): 252\u2013271","journal-title":"SIAM Journal on Computing"},{"key":"48_CR23","unstructured":"D.B. West (2000). Introduction to Graph Theory. Prentice Hall."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0048-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0048-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0048-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T23:05:11Z","timestamp":1562195111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0048-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,21]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["48"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0048-2","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,21]]}}}