A method for bounding the number of times a loop is executed via information theory

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:

$\displaystyle \text{while } A \text{ do } B$

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

Imagine that Alice has a random string ${s}$, 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 ${s}$.

This bounds the time of loop. Suppose that the loop goes on too long. Then, Alice would have found a method to send ${r}$ random bits to Bob, by sending him less than ${r}$ 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.