A report on Rabin’s 80th celebration

Les, Mitz, and Salil did a great job organizing the 80th birthday conference for Michael Rabin—that is Les Valiant, Michael Mitzenmacher, and Salil Vadhan.

Today I want to give some of the highlights, and there were many, of this wonderful gathering.

The conference was almost a washout—literally. Hurricane Irene caused many disruptions and ultimately made both Dana Scott and Moshe Vardi unable to attend and speak. The first morning had to be canceled. Yet the show did go on, and all agreed that Les’ cool head made everything work: times were changed, talks were reordered, speakers were calmed down, and it all happened.

I think my experience was fairly typical: I made and changed flights multiple times, finally taking an early early flight to Boston on Monday. Rivest had a difficult drive due to family issues arising from Irene, Wigderson drove from a flooded house in Princeton, and Yonatan Aumann arrived literally minutes before giving the last talk of the conference. This was the last, but perhaps the coolest talk, since it was on how to cut a birthday cake.

Michael is a rare and wonderful leader of the field of computer theory and much more. The talks were video-taped—do we soon have to say “video-flashed?”—and will be available to all eventually. The slides of the talks will also be up on the conference website soon.

I have known Michael since I was a graduate student at CMU, but never had the pleasure of taking a course with him. One of the recurrent themes were the raves by many who did have the honor of taking a class with him. They all had great memories, and great stories of his wonderful teaching style. Color me green with envy.

The Talks

There were many talks given in Michael’s honor. I can report that all but one was wonderful, and I saw all but one. It seems that I was talking during the remaining one—I hope it was OK, but let others decide that. I can say that I have rarely seen a series of such interesting talks, such well presented talks, and such fun. If you missed them live, I hope the video does show that they were all terrific.

Here are some of the highlights of some of the talks:

Richard Karp: Richard gave the first talk. While it was not called the “keynote” of the conference, I think that it set the tone for the conference, and was a great talk. He started by saying some extremely warm and kind remarks about the influence Michael has had both on him personally and on the field of computer science in general.

Karp’s talk centered on on of the great open problems in computing. No not that problem: the question was why do heuristics work so well in practice? The theory lags very far behind in giving reasons why large optimization problems can be solved fast and often with little or no error. Dick then gave some details on an approach he has been taking to this problem, but beyond these initial results I think the central question should be studied more intensively then it has so far.

Madhu Sudan: Madhu gave a beautiful technical talk on property testing. The main insight was some new insights into the question: why are some properties testable in sub-linear time and others are not?

Michael Mitzenmacher: Mitz talked about an “old” paper of Rabin’s from 1989. Mitz explained in a convincing manner how Rabin’s ideas of this paper were way ahead of their time, and how many breakthroughs in coding theory—Tornado codes for example—could be traced back to Rabin’s insights.

Not so old when you realize Michael was nearly 60 when he wrote it.

Rabin pointed out at the end of the talk that such error correction methods could play a greater role in the future in making DRAM memory chips.

Tal Rabin: She is Michael’s oldest daughter and is the manager of the Cryptography Research Group at IBM Yorktown. She gave a beautiful mixture of tales of growing up as his daughter and stories about cryptography. The talk was titled:

Michael and Me—related works.

It was wonderful to hear some of her personal stories of Michael as a parent, a grandparent, and once as a co-author.

Silvio Micali: Silvio presented a model he has been working on recently on how to approach auctions without any Bayesian assumptions. I will not do justice to his insights, but roughly the idea is to throw away distribution assumptions. They are replaced by sets of possible beliefs of opponents—the key is that these sets do not have prior probabilities. He is able to prove that his model allows new insights into auctions and other economic problems.

David Parkes: David spoke on crypto and auctions, with the main issue being the auctions’ integrity. As auctions become a dominant method of buying and selling goods, it is clear that knowing that cheating does not occur is critical.

Ron Rivest: Ron gave a new model, along with an interesting game called FlipIt. The game is an attempt to model the real world of security, where systems are broken and then repaired and broken again. This attack, defend, attack, defend, cycle cannot be stopped, it seems. But Ron’s game is a model of how the attacker and the defender should play. The model is new, seems quite interesting, and raises many open problems.

Avi Wigderson: Avi has a style that few can duplicate. He can make ideas that are deep seem easy, while presenting not a full proof, but just the right intuition of why something is true. Even if the full proof is long and complex, Avi can succeed in making you see the proof. With a single meta-slide he laid out a multitude of results about finite state automata, including classic and non-classic results.

Michael Ben-Or: Michael talked about the power of randomization in distributed systems. This thread of work was started by Rabin, and continues to be an important area. The shock is that “impossible” distributed algorithms are possible if randomization is allowed. Also many deterministic algorithms can be vastly improved in performance if randomization is allowed.

Salil Vadhan: Salil gave a terrific talk on the care and feeding of one-way-functions (OWF). He showed how to tremendously improve both the bounds and the proofs of results of the form: if there are OWFs, then X is possible. He explains why the existing results work, in a way that makes it sound simple, yet does not diminish these extremely important results.

Yonatan Aumann: Yonatan arrived, as I said, just in time to give the last talk on cutting a cake. This is a well-studied problem, with many published papers and whole books devoted to the topic. He showed that there were some very interesting new questions that had surprising answers. One of the coolest results showed that for certain situations there was no good division of the cake—that is, all divisions would violate some notion of fairness. But if some of the cake could be thrown away, then there was a division that was fair in a very strong sense. He called this dumping. Several of us pointed out to him at the end of his talk, and later off-line, that while this was a beautiful idea, he needed a better name. Rivest suggested calling the method the set-aside method.

Open Problems

One open problem to me is how does Rabin stay so sharp? He is eighty years old, his actual birthday was September 1, but he seems to me unchanged. He is full of ideas, is working on many projects, is teaching, and still as excited as ever about theory. How does he do it?

Happy Birthday again to Michael, and I hope there are many more celebrations in the future.

Finally, I would like to thank Les, Mitz, and Salil again for inviting me and letting me be part of this celebration.