For more information on Steve Mahaney's untimely demise
see
here.
Mahaney's theorem is
If there is a set S that is both sparse and NP complete
then P=NP
Lance 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 NPcomplete 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 NPhard under bttreductions then P=NP.
On PolynomialTime Bounded TruthTable 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 OgiwaraWatnabe 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 btthard 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 NPhard 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 NPhard under Turing reductions then
PH collapse further. (Complicated to state exactly how much further).
Competing Provers Yield Improved KarpLipton Collapse Results,
by Cai and Chakaravarthy and Hemaspaandra and Ogihara,
INFCTRL, 2005, V. 198

If there is a sparse set complete for P under logspace manyone 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)

Posted By GASARCH to Computational Complexity at 6/29/2007 04:23:00 PM