{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:32:36Z","timestamp":1787340756647,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>A Boolean function $f:\\{0,1\\}^n \\mapsto \\{0,1\\}$ is said to be $\\varepsilon$-far from monotone if $f$ needs to be modified in at least $\\varepsilon$-fraction of the points to make it monotone. We design a randomized tester that is given oracle access to $f$ and an input parameter $\\varepsilon&gt;0$ and has the following guarantee: It outputs \\sf Yes if the function is monotonically nondecreasing and outputs \\sf No with probability $&gt;2\/3$, if the function is $\\varepsilon$-far from monotone. This nonadaptive, one-sided tester makes $O(n^{7\/8}\\varepsilon^{-3\/2}\\ln(1\/\\varepsilon))$ queries to the oracle.<\/jats:p>","DOI":"10.1137\/13092770x","type":"journal-article","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T12:59:48Z","timestamp":1461761988000},"page":"461-472","source":"Crossref","is-referenced-by-count":14,"title":["An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube"],"prefix":"10.1137","volume":"45","author":[{"given":"D.","family":"Chakrabarty","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":[[2016,4,27]]},"reference":[{"key":"atypb1","first-page":"1704","volume":"31","author":"Ailon N.","year":"2006","journal-title":"Random Structures Algorithms"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2765-1"},{"key":"atypb4","unstructured":"D. Chakrabarty and C. Seshadhri,\n                      Optimal Bounds for Monotonicity and Lipschitz Testing Over the Hypercube\n                      , Tech. report TR12-030, ECCC, 2012."},{"key":"atypb5","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                      , Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 1999, pp. 97-108.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, and R. Rubinfeld,\n                      Monotonicity testing over general poset domains\n                      , in Proceedings of the 34th Annual ACM Symposium on the Theory of Computing (STOC), 2002, pp. 474-483.","DOI":"10.1145\/509907.509977"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20211"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3148"},{"key":"atypb12","first-page":"101","volume":"10","author":"Margulis G. A.","year":"1974","journal-title":"Problemy Peredachi Informatsii"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"D. Ron, R. Rubinfeld, S. Safra, and O. Weinstein,\n                      Approximating the influence of monotone Boolean functions in $O(\\sqrt{n})$ query complexity\n                      , in Proceedings of the 15th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2011.","DOI":"10.1007\/978-3-642-22935-0_56"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/13092770X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:41Z","timestamp":1787338001000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/13092770X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/13092770X"],"URL":"https:\/\/doi.org\/10.1137\/13092770x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}