Muli, Dor and Subash, Jerusalem May 21 2015.
Michel Talagrand Gregory Margulis
In this post I will tell you about a new paper by Subhash Khot, Dor Minzer and Muli Safra entitled: On Monotonicity Testing and Boolean Isoperimetric type Theorems. This remarkable paper gives a definite answer to one of the main open problems on property testing, proves some wonderful new isoperimetric inequalities, and shed some light on the still mysterous property of monotonicity.
Property testing is an exciting area which lies between mathematics and the theory of computing. (Closely related to PCP and to some modern aspects of error-correcting codes.) Here is a post about it in Terry Tao’s blog.
Suppose that you have an unknown graph G and you want to distinguish between two possibilities
1) The graph G contains a triangles
2) We can remove an 1% of the edges of G so that no triangle will remain.
It turns out that by looking at a bounded number of edges drawn at random we can either demonstrate that G contains a triangle or demonstrate that with high probability the second possibility holds! Moreover, this is a deep mathematical result.
Property testing resembles a little election polls (and, more generally statistical hypothesis testing): We can estimate the outcomes of the election with good accuracy and high probability by probing the votes of a bounded number of voters.
Given a Boolean function f, what is the smallest number of queries needed to be able to say
1) The function f is not monotone:
2) With high probability f is at most ε-far from monotone, namely, it can be made monotone by flipping the value of at most values.
We will denote by ε(f) the normalized Hamming distance distance of a Boolean function f to the set of monotone functions.
A brief incomplete history of monotone testing
1) Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301–337, 2000.
This paper considered the tester: Choose x and y at random such that y > x test if f(y) < f(x).
Using the basic edge isoperminetric inequality it was proved that n queries suffice.
It tooks 15 years a new tester and a new isoperimetric inequality to break this record and show that queries suffice.
2) Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 411–418, 2013.
An improvement to was achieved here
3) Xi Chen, Rocco Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In Annual Symposium on Foundations of Computer Science, FOCS ’14, 2014.
The paper by Khot, Minzer and Safra reduces this to the optimal (apart from powers of logn) .They use yet a new tester and a new isoperimetric inequality.
I did not talk about adaptive version of the problem about lower bounds and about the dependence on . Khot, Minzer and Safra also give (up to powers of log) optimal dependence on .
Isoperimetric results: Margulis, Talagrand, and beyond
Margulis’s Theorem: Let f be a Boolean function on . Let $\latex \mu$ be the uniform probability measure on $\Omega_n$. For define
Now, the edge boundary (or total influence) of f is defined by
it is also denoted by .
The vertex boundary of f is defined by
The classic edge-isoperimetric result asserts that
Here var(f), is the variance of f.
Margulis theorem asserts that for some constant C:
In fact Margulis proved the result in greater generality for Bernoulli probability measures defined by where .
Again Talagrand’s theorem extends to the Bernoulli case. Talagrand’s theorem implies Margulis’ theorem by a simple application of the Cauchy-Swarz inequality. Continue reading