An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
Authors:
- D. ChakrabartyDCD. Chakrabarty
- C. SeshadhriCSC. Seshadhri
- 1 January 2016
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 45 (2) , 461-472
Abstract
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>0$ and has the following guarantee: It outputs \sf Yes if the function is monotonically nondecreasing and outputs \sf No with probability $>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.
Keywords
This publication has 11 references indexed in Scilit:
- Property Testing Lower Bounds via Communication Complexitycomputational complexity, 2012
- Monotonicity testing and shortest-path routing on the cubeCombinatorica, 2012
- Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity2011
- Testing monotonicity over graph productsRandom Structures & Algorithms, 2008
- Tolerant property testing and distance approximationJournal of Computer and System Sciences, 2006
- On Disjoint Chains of SubsetsJournal of Combinatorial Theory, Series A, 2001
- Spot-CheckersJournal of Computer and System Sciences, 2000
- Testing MonotonicityCombinatorica, 2000
- Improved Testing Algorithms for Monotonicity1999
- Optimal numberings and isoperimetric problems on graphsJournal of Combinatorial Theory, 1966