Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-011 | 22nd January 2015 15:19

#### On Monotonicity Testing and Boolean Isoperimetric type Theorems

TR15-011
Authors: Subhash Khot, Dor Minzer, Muli Safra
Publication: 22nd January 2015 15:21
give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function
$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from