Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-011 | 22nd January 2015 15:19

On Monotonicity Testing and Boolean Isoperimetric type Theorems

RSS-Feed




TR15-011
Authors: Subhash Khot, Dor Minzer, Muli Safra
Publication: 22nd January 2015 15:21
Downloads: 4628
Keywords: 


Abstract:

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we
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
being monotone with constant probability.



ISSN 1433-8092 | Imprint