{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:46Z","timestamp":1759638226375},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_8","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T11:25:55Z","timestamp":1286450755000},"page":"142-157","source":"Crossref","is-referenced-by-count":9,"title":["Property Testing of Massively Parametrized Problems \u2013 A Survey"],"prefix":"10.1007","author":[{"given":"Ilan","family":"Newman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3-4","key":"8_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.10056","volume":"21","author":"N. Alon","year":"2002","unstructured":"Alon, N.: Testing subgraphs in large graphs. Random Struct. Algorithms\u00a021(3-4), 359\u2013370 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"8_CR2","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 Journal on Computing\u00a030, 1842\u20131862 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Transitive-closure spanners. In: SODA, pp. 932\u2013941 (2009)","DOI":"10.1137\/1.9781611973068.101"},{"issue":"1","key":"8_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. Comput.\u00a035(1), 1\u201321 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1002\/rsa.10023","volume":"20","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Ron, D.: Testing properties of directed graphs: acyclicity and connectivity. Random Struct. Algorithms\u00a020(2), 184\u2013205 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-540-74208-1_28","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Chakraborty","year":"2007","unstructured":"Chakraborty, S., Fischer, E., Lachish, O., Matsliah, A., Newman, I.: Testing s-t -connectivity. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 380\u2013394. Springer, Heidelberg (2007)"},{"issue":"3","key":"8_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I. Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM\u00a054(3), 12 (2007)","journal-title":"J. ACM"},{"key":"8_CR8","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. BEATCS: Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"BEATCS: Bulletin of the European Association for Theoretical Computer Science"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proceedings of the 34th ACM STOC, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"key":"8_CR10","unstructured":"Fischer, E.: Personal communication"},{"issue":"1","key":"8_CR11","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. Inf. Comput.\u00a0189(1), 107\u2013116 (2004)","journal-title":"Inf. Comput."},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-3-540-85363-3_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Lachish, O., Matsliah, A., Newman, I., Yahalom, O.: On the query complexity of testing orientations for being Eulerian. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 402\u2013415. Springer, Heidelberg (2008) (to appear in Algorithmica)"},{"key":"8_CR13","unstructured":"Fischer, E., Lachish, O., Newman, I., Rosenberg, E.: Lower bound technique for properties of underlying graphs. In Preparations"},{"key":"8_CR14","unstructured":"Fischer, E., Lachish, O., Nimbhorkar, P.: In Preparations"},{"issue":"4","key":"8_CR15","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. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"8_CR16","unstructured":"Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing orientation properties. Electronic Colloquium on Computational Complexity (ECCC) (153) (2005)"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing properties of constraint-graphs. In: IEEE Conference on Computational Complexity, pp. 264\u2013277 (2007)","DOI":"10.1109\/CCC.2007.31"},{"key":"8_CR18","first-page":"37","volume":"38","author":"A. Kostochka","year":"1982","unstructured":"Kostochka, A.: The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz.\u00a038, 37\u201358 (1982)","journal-title":"Metody Diskret. Analiz."},{"issue":"1","key":"8_CR19","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/s00037-008-0239-z","volume":"17","author":"O. Lachish","year":"2008","unstructured":"Lachish, O., Newman, I., Shapira, A.: Space Complexity vs. Query Complexity. Computational Complexity\u00a017(1), 70\u201393 (2008)","journal-title":"Computational Complexity"},{"issue":"5","key":"8_CR20","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1137\/S009753970038211X","volume":"31","author":"I. Newman","year":"2002","unstructured":"Newman, I.: Testing membership in languages that have small width branching programs. SIAM J. Comput.\u00a031(5), 1557\u20131570 (2002)","journal-title":"SIAM J. Comput."},{"key":"8_CR21","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 Press, Dordrecht (2001)"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1017\/S0305004100061521","volume":"95","author":"A. Thomason","year":"1984","unstructured":"Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc.\u00a095, 261\u2013265 (1984)","journal-title":"Math. Proc. Cambridge Philos. Soc."}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T11:22:26Z","timestamp":1553167346000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}