Events Fall 2014

TCS+ Online Seminar

Apr 29, 2015 10:00 am – 11:00 am 

Add to Calendar


Muli Safra (Tel Aviv University)


Calvin Lab 116

On Monotonicity Testing and Boolean Isoperimetric type Theorems

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 ~O(sqrt(n)/eps^2) non-adaptive queries to a n-variate Boolean function f, always accepts a monotone function and rejects a function that is eps-far from being monotone with constant probability.

Joint work with Subhash Khot and Dor Minzer. (Paper available on ECCC.)