I am breaking weblog silence to bring the very sad news of the loss of a co-author, good friend and great complexity theorist Stephen Mahaney. Steve passed away Tuesday afternoon from complications from a stroke. He was in his late 50's.
Mahaney received his Ph.D. in 1981 at Cornell under Juris Hartmanis. He has worked at Penn State, AT&T Bell Labs, the University of Arizona, DIMACS (where he served as associate director) and the National Science Foundation as a senior advisor in the CISE directorate.
Mahaney is best know for the theorem that bears his name, that there are no small NP-complete sets unless P = NP. He's had a number of other papers including four with co-authors Stuart Kurtz and Jim Royer looking at many aspects of the isomorphism conjecture including their JACM paper that showed it failed relative to a random oracle.
Mahaney co-founded what is now the IEEE Conference on Computational Complexity and was PC chair of the second conference in 1987.
Last time I visited Steve at the NSF he wouldn't let me buy him a beer citing Federal rules against receiving gifts. But I'll buy one for him tonight. Godspeed Mahaney.