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/