Fast foward to the summer of 1987. Neil Immerman shows that nondeterminstic space is closed under complement. He sends the paper to Mike Sipser at MIT, where I was a grad student at the time. Mike was in Russia and we didn't find out about the result at MIT until we got an email talk announcement about it at Berkeley. It wasn't for several months that we found out the same result was proven at about the same time by Slovakian undergrad R�bert Szelepcs�nyi.
Much ado was made about how fast the results on interactive proof systems and probabilistically checkable proofs were distributed during 1990-92. Hardly anyone raises an eyebrow on how fast the primality results spread despite that they came from a "third-world country". Manindra Agrawal sends out an email on Sunday, August 4. By Monday the results are verfied, discussed and at least one seminar presented the result. By Thursday there was an article in the New York Times. Now three weeks later, the primality result seems like old news. Sure Manindra and his students had this nice algorithm for primality but what have they done lately?
During the week of August 4 I was on vacation and missed all of the fun. When I retured mixed in with about 50 emails on primality, were 2 emails annoucing the death of Edsger Dijkstra. Dijkstra hasn't been an active member of the theory community for a long time and I don't believe I ever met him. However, his polynomial-time algorithm for shortest path will have more practical applications than the polynomial-time algorithm for primality ever will.
Post a Comment