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/