{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:19:23Z","timestamp":1725567563166},"publisher-location":"Berlin, Heidelberg","reference-count":31,"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_29","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"346-354","source":"Crossref","is-referenced-by-count":0,"title":["Local Property Reconstruction and Monotonicity"],"prefix":"10.1007","author":[{"given":"Michael","family":"Saks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"11","key":"29_CR1","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1016\/j.ic.2006.06.001","volume":"204","author":"N. Ailon","year":"2006","unstructured":"Ailon, N., Chazelle, B.: Information theory in property testing and monotonicity testing in higher dimension. Information and Computation\u00a0204(11), 1704\u20131717 (2006)","journal-title":"Information and Computation"},{"issue":"3","key":"29_CR2","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1002\/rsa.20167","volume":"31","author":"N. Ailon","year":"2007","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Estimating the distance to a monotone function. Random Structures and Algorithms\u00a031(3), 371\u2013383 (2007)","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"29_CR3","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/s00453-007-9075-9","volume":"51","author":"N. Ailon","year":"2008","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Property-preserving data reconstruction. Algorithmica\u00a051(2), 160\u2013182 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"29_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. SIAM Journal on Computing\u00a039(1), 143\u2013167 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"29_CR5","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1137\/06064888X","volume":"37","author":"N. Alon","year":"2008","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing\u00a037(6), 1703\u20131727 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"29_CR6","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica\u00a023(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"issue":"4","key":"29_CR7","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1002\/rsa.20300","volume":"56","author":"T. Austin","year":"2010","unstructured":"Austin, T., Tao, T.: Testability and repair of hereditary hypergraph properties. Random Structures and Algorithms\u00a056(4), 373\u2013463 (2010)","journal-title":"Random Structures and Algorithms"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual Symposium on Theory of Computing (STOC), pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: PP has subexponential time simulations unless EXP-TIME has publishable proofs. Computational Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"issue":"1","key":"29_CR10","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.ic.2004.10.001","volume":"196","author":"T. Batu","year":"2005","unstructured":"Batu, T., Rubinfeld, R., White, P.: Fast approximate PCPs for multidimensional bin-packing problems. Information and Computation\u00a0196(1), 42\u201356 (2005)","journal-title":"Information and Computation"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners. In: Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA), pp. 531\u2013540 (2009)","DOI":"10.1137\/1.9781611973068.101"},{"issue":"3","key":"29_CR12","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences\u00a047(3), 549\u2013595 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. Journal of the ACM\u00a045, 965\u2013981 (1998)","journal-title":"Journal of the ACM"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-48413-4_10","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"Y. Dodis","year":"1999","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol.\u00a01671, pp. 97\u2013108. Springer, Heidelberg (1999)"},{"issue":"3","key":"29_CR15","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"6","author":"F. Ergun","year":"2000","unstructured":"Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. Journal of Computer Systems and Sciences (JCSS)\u00a06(3), 717\u2013751 (2000)","journal-title":"Journal of Computer Systems and Sciences (JCSS)"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Fattal, S., Ron, D.: Approximating the distance to monotonicity in high dimensions. ACN Trans. on Alg.\u00a06(3) (2010)","DOI":"10.1145\/1798596.1798605"},{"key":"29_CR17","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 EATCS\u00a075, 97\u2013126 (2001)","journal-title":"Bulletin of EATCS"},{"issue":"1","key":"29_CR18","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(1), 107\u2013116 (2004)","journal-title":"Information and Computation"},{"key":"29_CR19","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 Annual Symposium on Theory of Computing (STOC), pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing\/correcting for polynomials and for approximate functions. In: Proceedings of the 23rd Annual Symposium on Theory of Computing (STOC), pp. 32\u201342 (1991)","DOI":"10.1145\/103418.103429"},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorial property testing - a survey. In: Randomization Methods in Algorithm Design, pp. 45\u201360 (1998)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samordinsky, A.: Testing monotonicity. Combinatorica\u00a020, 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"4","key":"29_CR23","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. Journal of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"29_CR24","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1002\/rsa.20211","volume":"33","author":"S. Halevy","year":"2008","unstructured":"Halevy, S., Kushilevitz, E.: Testing monotonicity over graph products. Random Structures and Algorithms\u00a033(1), 44\u201367 (2008)","journal-title":"Random Structures and Algorithms"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the 32th Annual Symposium on Theory of Computing (STOC), pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"issue":"72","key":"29_CR26","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","volume":"6","author":"M. Parnas","year":"2006","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. Journal of Computer and System Sciences\u00a06(72), 1012\u20131042 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR27","doi-asserted-by":"crossref","unstructured":"Ron, D.: Property testing. In: Handbook on Randomization, vol.\u00a0II, pp. 597\u2013649 (2001)","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"29_CR28","doi-asserted-by":"publisher","first-page":"647","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 Journal of Computing\u00a025, 647\u2013668 (1996)","journal-title":"SIAM Journal of Computing"},{"key":"29_CR29","unstructured":"Saks, M., Seshadhri, C.: Parallel monotonicity reconstruction. In: Proceedings of 19th Annual Symposium on Discrete Algorithms (SODA), pp. 962\u2013971 (2006)"},{"issue":"7","key":"29_CR30","doi-asserted-by":"publisher","first-page":"2897","DOI":"10.1137\/080728561","volume":"39","author":"M.E. Saks","year":"2010","unstructured":"Saks, M.E., Seshadhri, C.: Local monotonicity reconstruction. SIAM Journal on Computing\u00a039(7), 2897\u20132926 (2010)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"29_CR31","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences\u00a062(2), 236\u2013266 (2001)","journal-title":"Journal of Computer and System Sciences"}],"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_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T12:48:23Z","timestamp":1636634903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}