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.


4 Comments to “Monotonicity testing”

  1. А текущие тесты более хитрые?

    И да, тебе не стремно публиковать в широком доступе задачу, которую очень надеешься решить? 🙂

    • The second open problem given by Sofya was to construct another test =) However, my intuition is that it is hardly possible.

      No, this problem is more than 10 years old now and was given a lot of times, I suppose =) I tried really hard to solve it, but still have no idea. Now, when I am waiting for an offer from Penn State, I can challenge other people with it. If somebody manages to solve it, it can be a good argument if he or she applies to Penn State and can probably make a paper by itself.

      In fact, the real beauty of the problem is that it gives an example of how an algorithmic question can be turned into nice combinatorial problem. I think this example should be available to community.

  2. Ну более-менее все известные мне примеры property testing алгоритмов обладают такой красотой. Так что это особенность области скорее.

    • Yes, you’re right. There is also another kind of beauty in these — they deal with well-known problems in somewhat unexpected ways. There was even a mini-workshop on Innovations in Computer Science 2010 ln property testing, where this can be seen.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: