March 10, 2010

Monotonicity testing

This is a post about an open problem that was given to me by Sofya Raskhodnikova last summer. The problem turned out to be rather difficult and I still don’t know the solution. Even on mathoverflow I got no answer about what methods to try. However, it can be described rather easily (you can see the description following the link to mathoverflow).

Here I will try to explain (very informally) what it has to do with algorithms and particularly testing monotonicity in sublinear time. I suppose that you have read the description of the problem.

Now suppose that we are trying to test a function for monotonicity using the following test: picking an edge of the hypercube at random and querying the values on its ends, if the edge is not monotone then we say “NO”, otherwise we continue the process. After some iterations we stop and say “YES”.

The problem is to prove that if the function is $\epsilon$-far from being monotone then after small number of iterations we will find a non-monotone edge with high probability. Here $\epsilon$-far means as usually with property testing problems that the minimal fraction of vertices at which the value of the function needs to be changed to make it monotone is $\epsilon$. So we want to show that if there are many vertices, where the values need to be changed to make the function monotone, then there must be many non-monotone edges. Turning to contrapositive: if there are just a few edges then we can change values in a small number of vertices to make the function monotone. This is exactly what the described open problem is about.