Adaptive Boolean Monotonicity Testing in Total Influence Time
Not on the map. Why?
Abstract (arXiv)
The problem of testing monotonicity of a Boolean function f:0,1n → 0,1 has received much attention recently. Denoting the proximity parameter by varepsilon, the best tester is the non-adaptive widetildeO(√n/varepsilon2) 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(varepsilon-1log n).
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 9 Jan 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2023: 1.
1 paper.