# On monotonicity testing and boolean isoperimetric type theorems

 Computer Science/Discrete Mathematics Seminar I Topic: On monotonicity testing and boolean isoperimetric type theorems Speaker: Subhash Khot Affiliation: New York University Date: Monday, February 2 Time/Room: 11:15am - 12:15pm/S-101 Video Link: http://video.ias.edu/csdm/2015/0202-SubhashKhot

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. Joint work with Dor Minzer and Muli Safra. The paper is available on ECCC: http://eccc.hpi-web.de/report/2015/011/