Description
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.)
All scheduled dates:
Upcoming
No Upcoming activities yet