Wednesday, September 24, 2008

Mike66, Remembered.

Mike66, from the way Mike looked, was like Mike30's. The opening speaker quipped how Mike got U. Warwick to build a physical bridge between the Math and CS depts.

Leslie Valiant gave the first technical talk. His basic premise is that evolution is an algorithmic process and we need a model that will converge in rate commensurate with the growth rate of DNAs and explain the complexity of current organisms. He presented a model that is contained in PAC learning. Michael Fischer, a long term collaborator of Mike, followed and spoke about the think-a-dot puzzle, its states, strings it generates, and their properties. Mike used this construct in 70's to teach finite state machines. Graham Cormode started with theMunro+Paterson result from 80's, the earliest truly streaming result, and spoke about medians, in small space, small number of passes, whatever.

Mike designed and released a puzzle weeks earlier. He described the solutions over time as they arrived, using pseudonyms, and the finale revealed that Pie Goly who solved the Pie Gon puzzle was Vaughan Pratt.

Don Knuth charmingly started with simple Y functions and when he was done, they had become as detailed, intimidating and rich as multi-starred problems in his book. For appetizer, he showed how to get 66 from digits 1,...,9 using binary operations +,-,*,/. (He wrote a program to evaluate all such expressions.) Cenk Sahinalp revealed a secret: you can beat Mike by cheating, and demonstrated how to improve the classic Masek-Paterson edit distance computation, by changing the problem and using approximations. Uri Zwick, in a short, explosive pst, described the Overhang result, an ode to proof by pictures! Kurt Melhorn made an optimization problem out of assigning review papers to PC members.

There were other great talks of course. What remains on my mind is that researchers came from Tokyo, Boston and even non-baseball towns. They came to describe their interaction with Mike which in most cases had an aspect of puzzle solving. So, differences in age, generation and research area faded away; only the love for problems, puzzles and proofs remained floating. I think everyone was happy with that.

Thanks to Artur Czumaj, Leslie Goldberg and Uri Zwick for pulling this together. The artwork is sculpture by Le Page. In a social context, I enjoyed discussing the state of the world with the ever-reasoning Josep Diaz, and sharpening each others' arguments.


Post a Comment

<< Home