While Lance was AT Mikefest (Sipser's 60th Bday conference), helping to organize it, emceeing the personal statements, I was... also there.
A few notes
- Aside from his graying hair, Mike still looks like a teenager.
- In 1985 Mike was one of the few people who thought P=BPP. He wrote a paper about how a certain kind of expander implies what we would now call a hard vs randomness result and presented it at the 1986 CCC (called STRUCTURES then). After the Nisan-Wigderson Hard vs Rand results most everyone thought P=BPP. But Mike was there first.
- I took his grad complexity class in the early 1980's. I remember him proving results that either he or someone else had JUST proven the last week. He did a good job too! What struck me then and now is how vibrant CS is as a field that material taught LAST WEEK can be in an INTRO grad course (that's not as true anymore).
- After PARITY not in AC_0, and the monotone circuit results, Sipser and others were OPTIMISTIC that P vs NP would be solved ``soon''. Oh, to be in a field in the early days when people were optimistic. But see next point.
- Mike claims he STILL thinks P vs NP will be solved in 20 years. I don't quite know if he REALLY thinks this or wants to make the point that we should be optmistic. Similar to Lipton thinking P=NP--- does he really think that or does he want to make the point that we shouldn't all be so sure of ourselves?
- Steve Rudich told me that I misquoted him in a blog post and people often say `Steve, do you really think we are 6 months from an independence result'. I am not surprised that I made a MISTAKE in a blog post. I am surprised that people read it, remembered it, and asked him about it. In any case I have edited that post to SAY it was a mistake and I re-iterate it now: STEVE RUDICH DOES NOT THINK WE ARE SIX MONTHS AWAY FROM AN IND PROOF FOR P VS NP.
- I spoke to Mauricio Karchmer who, with Avi W and others, had an approach to P vs NC^1 via comm. comp which at the time I thought was very promising--- since we really can prove things in comm. comp. Alas it still has not panned out. However, Mauricio now thinks that (1) We can't prove lower bounds because they are false, and (2) we can't prove upper bounds because we are stupid.