{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:51:57Z","timestamp":1725889917027},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_39","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"426-437","source":"Crossref","is-referenced-by-count":0,"title":["Space Complexity vs. Query Complexity"],"prefix":"10.1007","author":[{"given":"Oded","family":"Lachish","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"publisher","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. on Computing\u00a030, 1842\u20131862 (2001)","journal-title":"SIAM J. on Computing"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. In: Proc. of FOCS 2005, pp. 429\u2013438 (2005)","DOI":"10.1109\/SFCS.2005.5"},{"key":"39_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. of STOC 2006, pp. 251\u2013260 (2006)","DOI":"10.1145\/1132516.1132555"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3-CNF properties are hard to test. In: Proc. of STOC 2003, pp. 345\u2013354 (2003)","DOI":"10.1145\/780542.780594"},{"key":"39_CR5","first-page":"549","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. JCSS\u00a047, 549\u2013595 (1993)","journal-title":"JCSS"},{"key":"39_CR6","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, E., Newman, I., Sgall, J.: Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. and Alg. (in press)","DOI":"10.1109\/CCC.2002.1004342"},{"issue":"4","key":"39_CR8","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 connection to learning and approximation. JACM\u00a045(4), 653\u2013750 (1998)","journal-title":"JACM"},{"issue":"1","key":"39_CR9","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":"39_CR10","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1109\/TIT.1972.1054893","volume":"18","author":"J. Justesen","year":"1972","unstructured":"Justesen, J.: A class of constructive asymptotically good algebraic codes. IEEE Transcations on Information\u00a018, 652\u2013656 (1972)","journal-title":"IEEE Transcations on Information"},{"key":"39_CR11","unstructured":"Lachish, O., Newman, I.: Languages that are Recognized by Simple Counter Automata are not necessarily Testable, ECCC report TR05-152"},{"key":"39_CR12","volume-title":"The Theory of Error-Correcting Codes","author":"F. MacWilliams","year":"1997","unstructured":"MacWilliams, F., Sloane, N.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1997)"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Newman, I.: Testing of functions that have small width branching programs. In: Proc. of 41th FOCS, pp. 251\u2013258 (2000)","DOI":"10.1109\/SFCS.2000.892112"},{"key":"39_CR14","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"39_CR15","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing. In: Handbook of Randomized Computing, vol.\u00a0II, pp. 597\u2013649. Kluwer Academic, Dordrecht (2001)"},{"key":"39_CR16","doi-asserted-by":"publisher","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. on Computing\u00a025, 252\u2013271 (1996)","journal-title":"SIAM J. on Computing"},{"key":"39_CR17","unstructured":"Sudan, M.: Lecture Notes on Algorithmic Introduction to Coding Theory, available at: http:\/\/theory.lcs.mit.edu\/~madhu\/FT01\/scribe\/lect6.ps"},{"key":"39_CR18","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/S0022-0000(75)80005-5","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G., Paterson, M.: Deterministic one-counter automata. Journal of Computer and System Sciences\u00a010, 340\u2013350 (1975)","journal-title":"Journal of Computer and System Sciences"}],"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\/11830924_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T16:21:23Z","timestamp":1683562883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11830924_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}