ECCC-Report TR15-011https://eccc.weizmann.ac.il/report/2015/011Comments and Revisions published for TR15-011en-usThu, 22 Jan 2015 15:21:15 +0200
Paper TR15-011
| On Monotonicity Testing and Boolean Isoperimetric type Theorems |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2015/011We 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.
Thu, 22 Jan 2015 15:21:15 +0200https://eccc.weizmann.ac.il/report/2015/011