Skip to content

Moser’s Method of Bounding a Program Loop

June 2, 2009

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.

3 Comments leave one →
  1. jmount permalink
    June 2, 2009 10:48 am

    What a great idea- I agree it will soon be a standard tool.

  2. kcode permalink
    June 4, 2009 2:27 pm

    Sorry, but I didnt get it. Can you elaborate it a bit more!😦

  3. rjlipton permalink*
    June 5, 2009 11:52 am

    Check out Lance’s blog for a more detailed version.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s