Moser’s Method of Bounding a Program Loop

Robin Moser just presented his award winning paper at STOC: “A Constructive Proof of the Lovász Local Lemma.” It was a great talk, as was Chris Peikert’s talk on his award winning paper: “Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem.”

I have to comment right away on Robin’s result. No actually not on his result, but on a method he used to bound the running time of an algorithm. I thought that it was one of the coolest ideas that I have seen in a long time. There are things close to what he did, but the exact argument seems novel to me.

I raised my hand at the end of his talk, and instead of a question I told him that I thought what he had done was brilliant. Many seemed to agree, and on the way out of the room, to lunch, I was pleased that Cynthia Dwork thanked me for my comment. We should, Cynthia and I agree, tell people how wonderful their work is, when it is deserved. And Robin’s work deserves it.

What He Did

Robin has a simple loop of the following form:

and as is usual, he needs to bound the number of times that is executed. There are many ways to do this, but here is how Robin did it.

Imagine that Alice has a random string , that Bob does not know. As the program loop is executed Alice sends messages to Bob, which allow Bob to get more and more of the random string .

This bounds the time of loop. Suppose that the loop goes on too long. Then, Alice would have found a method to send random bits to Bob, by sending him less than bits of messages. Since this is impossible, the loop must stop.

Robin can get a precise bound on the number of messages, and therefore on the number of executions of the loop.

This is just a very high level sketch of his method. I realize that it is not very detailed, but I think we should leave that to Robin. The main point is this: an information theory bound yields an upper bound on the running time of a computational process.

Open Problems

Robin promises to write this method up in detail soon, this is just a sketch. Look for it to be posted shortly. Also, plan on using this tool in future work, as it seems very powerful to me.