Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On Monotonicity Testing and Boolean Type Isoperimetric Inequalities
event speaker icon
Dor Minzer (Tel-Aviv University)
event date icon
Wednesday, 04.11.2015, 12:30
event location icon
Taub 201
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 function f, always accepts a monotone function and rejects a function that is \eps-far from being monotone with constant probability.