Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one meaningless since B trivially implies A. Not just a mere extension of A but B had a completely different proof of something much stronger. People will forget all about A--why bother when you have B? Too bad because A was such a nice breakthrough in its time.
Let me give two examples.
In STOC 1995 Nisan and Ta-Shma showed that Symmetric logspace is closed under complement. Their proof worked quite differently from the 1988 Immerman-Szelepcsenyi nondeterministic logpsace closed under complement construction. Nisan and Ta-Shma created monotone circuits out of undirected graphs and used these monotone circuits to create sorting networks to count the number of connected components of the graph.
Ten years later Omer Reingold showed that symmetric logspace was the same as deterministic logspace making the Nisan-Ta-Shma result an trivial corollary. Reingold's proof used walks on expander graphs and the Nisan-Ta-Shma construction was lost to history.
In the late 80's we had several randomized algorithms for testing primality but they didn't usually give a proof that the number was prime. A nice result of Goldwasser and Kilian gave a way to randomly generate certified primes, primes with proofs of primeness. Adleman and Huang later showed that one can randomly find a proof of primeness for any prime.
In 2002, Agrawal, Kayal and Saxena showed Primes in P, i.e., primes no longer needed a proof of primeness. As Joe Kilian said to me at the time, "there goes my best chance at a Gödel Prize".
The older results may still have value if their proof are easier. I supsect that Nisan-Ta-Shma (thats two people not three) is easier than Reingold's proof.
ReplyDeleteFor the results in primes not sure what is easier. And of course the original Miller-Rabin Prob Primes result is still used since people really do need to test primality fast.
Note to self -- do a post about when a result is subsumed but is still worth knowing.
Let's not forget that the same L=SL result of Omer Reingold overshadowed Trifonov's slightly weaker result, you actually wrote a blog post about it back in 2004: https://blog.computationalcomplexity.org/2004/12/bad-timing.html
ReplyDeleteAlthough Trifonov's technique can be applied to more general settings than the Zig-Zag technique.
The collapse of both the logarithmic alternation hierarchy and the logarithmic oracle hierarchy to their second levels were wiped out after few months by Immerman-Szelepcsényi.
ReplyDeleteI am very glad to see that you don't consider LFKN usurped by that retched non-relativizing algebraization business.
ReplyDelete