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.
STEVE RUDICH DOES NOT [THING] WE ARE SIX MONTHS AWAY FROM AN IND PROOF FOR P VS NP.
ReplyDeleteHowever, Mauricio now [things] that (1) We can't prove lower bounds because they are false, and (2) we can't prove upper bounds because we are stupid.
I got an email asking if I got Karchmer's quote backwards.
ReplyDeleteNo- he really did say that thel ower bounds we want are false and that we don't have algorithms because we are stupid, Of course, he may have been kidding.
No Bill, I was not kidding. And I only had one glass of wine at that point.
ReplyDeleteEvery new surprising algorithm we discover should be consider as evidence towards equality. I was surprised by some of the holographic algorithms. Avi W. pointed out once that these can be explained away by some argument that have to do with quantum computation. Still, the algorithms are surprising.
Perhaps Barrington's theorem is the first example of this. That was a real shocker to all of us that were trying to prove exactly the opposite.
So I would say, as much as we haven't made much progress on the lower bound front, I am not sure we have done much progress on the upper bound front either.
And Bill, it was great to see you and to be able to chat with you.
Will you tell us a little bit about the contents of the talks ?
ReplyDelete