Mahaney's theorem is
If there is a set S that is both sparse and NP complete then P=NPLance has already done a nice blog entry on this topic, so I will take this in a different direction.
I looked in Joel Seifras's theroy database for theory articles with the word `sparse' in them. I then edited it down to articles that relate directly or indirectly to Mahaney's theorem. While this is hard to make precise, there were over 100 articles that owe a debt of gratitude to Mahaney's papers (I do not know how many of them cited Mahaney's paper.)
I list the articles that seem most directly related to Mahaney's paper. I may have left out papers that ended up being superseded by papers on this list.
- If there is a sparse S that is NP-complete then P=NP. Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis, by Mahaney. 1982 JCSS, Vol 25. (earlier version in FOCS 1980, 25th FOCS)
- If there is a sparse S that is NP-hard under btt-reductions then P=NP. On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets, SICOMP 1991, V. 20 by Ogiwara and Watanabe (earlier version in STOC 1990, 22 STOC)
- An easier proof of Ogiwara-Watnabe paper with better bounds: On Reductions of NP Sets to Sparse Sets by Homer and Longpre. JCSS 1994, V. 48 (Earlier version in COMPLEXITY 1991)
- Generalize to counting classes. For example, if there is a set that is btt-hard for MOD_{2}P then MOD_{2}P=P On Sparse Hard Sets for Counting Classes. by Ogiwara and Lozano, TCS 1993, V. 112.
- If there is a sparse set that is NP-hard under Turing reductions then PH=\Sigma_{2}^{p} Some Connections Between Nonuniform and Uniform Complexity Classes, by Karp and Lipton, STOC 1982
- If there is a sparse set that is NP-hard under Turing reductions then PH collapse further. (Complicated to state exactly how much further). Competing Provers Yield Improved Karp-Lipton Collapse Results, by Cai and Chakaravarthy and Hemaspaandra and Ogihara, INFCTRL, 2005, V. 198
- If there is a sparse set complete for P under log-space many-one reductions then P=L. Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis, by Cai and Sivakumar, JCSS 1999, V. 58. (Earlier version in COCOON 1997)