Wednesday, June 27, 2007

Steve Mahaney

Guest post by Lance Fortnow

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.


  1. An incalculable loss. He was one of the original friendly faces of our field for me, more than 20 years ago. We have lost too many young (Carl Smith, Ron Book...) of those who worked to build for others---as he was doing at NSF, previously at DIMACS.

  2. i knew steve well at bell labs, where he was a brilliant, funny, and a good friend. steve had an unparalleled thirst for knowledge. the stars are dimmed by this tragic loss.

  3. What terrible news is this, I just learned, but I cannot yet wrap my mind around this. It seems almost impossible, but the impossible happens as well I guess. We will dearly miss this brilliant mind.


  4. I cannot yet believe Steve is gone.
    I have known Steve since Penn State days, and as a close colleague during his time at Arizona. He was a wonderful person and a great scientist who thought deeply about computational complexity and made many contributions to the field. Steve's many contributions in service to our field are illustrated by the many key posts he held and his many efforts in support of young scientists. We cannot afford to lose such leaders as Steve, and I deeply mourn his loss. Pete

  5. is the list of accepted papers to FOCS'07 available?

  6. Anonymous 5 missed a wonderful opportunity to say nothing. This is a tribute to Steve Mahaney, a great scientist, and a good friend to many of us.

  7. I talked to Steve on the phone just two months ago. There was some NSF business to discuss, but most of our conversation was spent just telling jokes, trading stories, and catching up (I hadn't talked with him in a while). I remember thinking afterward what a joy it is to have someone like him in our discipline. I will surely miss him.

    Kathryn remembers Mahaney's Minnesotan Etiquette Rule: When you offer a Minnesotan something, to be polite they must refuse twice and only accept if you ask a third time.

  8. I am shocked and so sad to read this news. Steve was my mentor at Arizona but more than that he was a friend. I had not heard of his passing until today when I realized I had not been in contact with him for over 2 years. I was going to ask him to visit our department and give a guest presentation. I remember the many hours we spent discussing academe and arguing pedagogical approaches to material... but what I will remember most is that he was one of the very few academics I ever met who was truly and honestly a wonderful human being as well as an impressive mind. I will have a guinness in his memory tonight.

    gary newell - NKU