{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:49Z","timestamp":1787340349713,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We investigate the problem of monotonicity reconstruction, as defined by Ailon et al. (2004) in a localized setting. We have oracle access to a nonnegative real-valued function f defined on the domain $[n]^d=\\{1,\\dots,n\\}^d$ (where d is viewed as a constant). We would like to closely approximate f by a monotone function g. This should be done by a procedure (a filter) that given as input a point $x\\in[n]^d$ outputs the value of $g(x)$, and runs in time that is polylogarithmic in n. The procedure can (indeed must) be randomized, but we require that all of the randomness be specified in advance by a single short random seed. We construct such an implementation where the time and space per query is $(\\log n)^{O(1)}$ and the size of the seed is polynomial in $\\log n$ and d. Furthermore, with high probability, the ratio of the (Hamming) distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n). This allows for a local implementation: one can initialize many copies of the filter with the same short random seed, and they can autonomously handle queries, while producing outputs that are consistent with the same approximating function g.<\/jats:p>","DOI":"10.1137\/080728561","type":"journal-article","created":{"date-parts":[[2010,5,5]],"date-time":"2010-05-05T18:08:16Z","timestamp":1273082896000},"page":"2897-2926","source":"Crossref","is-referenced-by-count":28,"title":["Local Monotonicity Reconstruction"],"prefix":"10.1137","volume":"39","author":[{"given":"Michael","family":"Saks","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,5,5]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20167"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9075-9"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"R7","unstructured":"T. Austin and T. Tao,\n                      On the testability and repair of hereditary hypergraph properties\n                      , Random Structures Algorithms, to appear."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy,\n                      Checking computations in polylogarithmic time\n                      , in Proceedings of the 23rd Annual Symposium on Theory of Computing (STOC), 1991, pp. 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.10.001"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.10.018"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. Woodruff,\n                      Transitive-closure spanners\n                      , in Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA), 2009, pp. 531\u2013540.","DOI":"10.1137\/1.9781611973068.101"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky,\n                      Improved testing algorithms for monotonicity\n                      , in Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 1999, pp. 97\u2013108.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"R17","unstructured":"S. Fattal and D. Ron,\n                      Approximating the distance to monotonicity in high dimensions\n                      , http:\/\/www.eng.tau.ac.il\/~danar\/Public-pdf\/app-mon-long.pdf, 2007."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky,\n                      Monotonicity testing over general poset domains\n                      , in Proceedings of the 34th Annual Symposium on Theory of Computing (STOC), 2002, pp. 474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/060652324"},{"key":"R20","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self-testing\/correcting for polynomials and for approximate functions\n                      , in Proceedings of the 23rd Annual Symposium on Theory of Computing (STOC), 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Combinatorial property testing\u2014A survey\n                      , Randomization Methods in Algorithm Design, 1998, pp. 45\u201360.","DOI":"10.1090\/dimacs\/043\/04"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Halevy and E. Kushilevitz,\n                      Testing monotonicity over graph products\n                      , Random Structures Algorithms, 33 (2008), pp. 44\u201367.","DOI":"10.1002\/rsa.20211"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"S. Kale, Y. Peres, and C. Seshadhri,\n                      Noise tolerance of expanders and sublinear expander reconstruction\n                      , in Proceedings of the 49th Foundations of Computer Science (FOCS), 2008, pp. 719\u2013728.","DOI":"10.1109\/FOCS.2008.65"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. Katz and L. Trevisan,\n                      On the efficiency of local decoding procedures for error-correcting codes\n                      , in Proceedings of the 32th Annual Symposium on Theory of Computing (STOC), 2000, pp. 80\u201386.","DOI":"10.1145\/335305.335315"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, London, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"D. Ron,\n                      Property testing\n                      , Handbook on Randomization, II, 2001, pp. 597\u2013649.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R33","unstructured":"M. Saks and C. Seshadhri,\n                      Parallel monotonicity reconstruction\n                      , in Proceedings of 19th Annual Symposium on Discrete Algorithms (SODA), 2006, pp. 962\u2013971."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080728561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:29Z","timestamp":1787337089000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080728561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":34,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080728561"],"URL":"https:\/\/doi.org\/10.1137\/080728561","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}