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.
Let me diverge and mention two other important results in this spirit. Bobkov’s theorem gives a sharp result when we consider the expectation of , rather than , where h(x) is defined just like I(x) but also for x so that f(x)=0.
Talagrand’s Influence-boundary theorem and conjecture
Let , where y is obtained from x by flipping the kth coordinate and let be the influence of the kth variable on f. (Sometimes the influence is defined as twice this number.)
Let . If f is monotone than II(f) is at most var (f).
Theorem (Talagrand 1997):
Talagrand conjectured that can be taken to be 1/2. Proving it would be great!
Here is a page with links to Talagrand’s preprints (in dvi forms) Talagrand’s hompage includes prize questions that he asked over the years.
Some new inequalities crucial for testing monotonicity
Following the first section of Khot, Minzer, and Safra’s paper I will briefly mention now isoperimetric inequalities related to monotonicity
Recall that ε(f) denote the normalized Hamming distance distance of a Boolean function f to the set of monotone functions.
Define when f(x)=0, and when f(x)=1
Thus, measures local violations of monotonicity. If f is monotone then for every x. Define . This quantity can be referred to as “total negative influence.”
Goldreich, Goldwasser, Lehman, Ron, Samorodnitsky
The first monotonicity testing result relied on an analog for the basic edge isoperimetric theorem.
Chakrabarty and Seshadhri.
We can define as the vertex boundary just for violations of monotonicity.
Khot, Minzer and Safra
Here the ~ means “up to polylogarithmic factors in n. (It will be very interesting to eliminate this little ~.)
I will end my description here. Chakrabarty and Seshadhri needed a further refinement of their inequality for their theorem, and Khot, Minzer, and Safra needed two further refinements and robust versions of their basic inequality in order to prove their goal. The proofs of the isoperimetric results and how to apply them for monotonicity testing are also very interesting.