Adaptive Boolean Monotonicity Testing in Total Influence Time
share
The problem of testing monotonicity of a Boolean function f:{0,1}^n →{0,1} has received much attention recently. Denoting the proximity parameter by ε, the best tester is the non-adaptive O(√(n)/ε^2) tester of Khot-Minzer-Safra (FOCS 2015). Let I(f) denote the total influence of f. We give an adaptive tester whose running time is I(f)poly(ε^-1 n).
READ FULL TEXT