NEXP and the Next Generation
Saluting Alan Selman upon the occasion of his retirement
Photos by Marty Kerker
Alan Selman is retiring after a long and illustrious career, the longest part spent alongside me in Buffalo. He arrived in August 1990, a year after me, and was hired as Chair. I was pleased to enact one of his first departmental decrees: “TGIF” parties. Before coming to Buffalo I’d experienced collegial gatherings with refreshments at Princeton, Oxford, and Cornell. So I happily volunteered to buy provisions every Friday morning at one of two gigantic grocery stores near the University, and lay out food and drink from 3:30 to 5. We kept it going for several years until it became unsustainable while the department’s growth made it impractical to squeeze everyone in to our one meeting room, in the building we had until two years ago.
Today Dick and I salute Alan’s technical and social contributions to Complexity Theory.
In Western New York we have the stamp of Juris Hartmanis and Alan acting effectively in concert. With Ron Book, Steve Mahaney, and Paul Young they co-founded the Computational Complexity conference which has run annually since 1986; the grant was mostly written in Alan’s living room. Lane Hemaspaandra and Jin-Yi Cai finished as students of Juris in 1986-87 just as I started a postdoc at Cornell. Lane went to Rochester, while later Alan brought Jin-Yi to Buffalo in 1993. Alan brought Mitsunori Ogihara to the United States on a postdoc to Buffalo, and Mitsu then earned a tenure-track position at Rochester and eventually became Chair there.
Lane and Mitsu and several of Alan’s past and current students joined most of my colleagues and many friends from Alan’s 24 years in Buffalo for his retirement party last Friday in UB’s Center For Tomorrow, which was the venue for the 1998 Complexity conference which I hosted.
Ashish Naik came all the way from California for the event, completing with Lane, Mitsu, and Alan the four authors of a paper that over 20 years ago solved the following problem:
Does every polynomial-time relation admit a function such that whenever holds, holds, and is computable in nondeterministic polynomial time?
The answer is that if yes, then the polynomial hierarchy would collapse to its second level. This is structural evidence of a ‘no’ answer overall. The proof drew on Alan’s notion of a P-selective set and theorem that self-reducibility places such a set into deterministic polynomial time.
Samik Sengupta drove from eastern Massachusetts. He was greatly stimulated when Alan brought Christian Glasser over on a postdoc ten years ago, as was I. All of these, however, were out-numbered by Alan’s current students. Here are three of them—Dung Nguyen, Andrew Hughes, and Nathan Russell—along with Hu Ding (second from left) and Edith Hemaspaandra and Lane:
I closed my own speech of appreciation by noting that whereas most retirees taper off their students, when one adds visiting student Nils Wisiol from Glasser’s group in Würzburg, Alan has the most he’s ever had. So in wishing Alan “many happy returns,” I said I was confident he will make many happy returns for his students’ defenses.
Our Chair Aidong Zhang opened and closed the remarks, with my colleagues Bill Rapaport and Atri Rudra following me, and then Ashish and Mitsu talking intimately about their collaboration and personal growth. UB President Satish Tripathi, himself a computer scientist with appointment in our department, also gave a welcome. Here are he and Aidong with Alan and his wife Sharon, who did work affiliated to Buffalo’s downtown medical campus and whom I’ve found a striking and friendly presence for over three decades.
That’s right—I met Alan for the first time with his whole family at ICALP 1982 in Aarhus, Denmark, which was my first conference after my first graduate year. I told some of the story from my post two years ago on the Even-Selman-Yacobi (ESY) Conjecture, named for Alan with Shimon Even and Yaacov Yacobi. Perhaps Hughes and I will take another swing this summer at showing it holds with respect to a random oracle—while the real prize we all sought 30 years ago, proving that public-key cryptography cannot leverage -hardness unless , remains elusive.
My remarks also looked back on the role of “structural” vis-à-vis “combinatorial” complexity, likening the latter with hindsight to the engine of a car and the former to the equally-indispensable transmission. (I had peeked at Mitsu’s speech noting the Selmans’ love of cars and ‘P NE NP’ license plate.) In the great scientific fact that the many thousands of computational problems all quantize into a few handfuls of completeness levels, the problems themselves are combinatorial, but the reducibility relationships and equivalences between them are structural. My purpose here however is to look forward rather than back, at what structural properties of reductions are saying about lower-bound frontiers.
We have covered Ryan Williams’ breakthrough separation of nondeterministic exponential time (that is, ) from non-uniform . This theorem leverages combinatorial results, but in itself is a careful application of structural ideas. With still resisting separation, what this does is heighten interest in these exponential-time classes. Enter Alan’s paper with Nguyen, which he just presented at the 2014 STACS conference.
The pivotal concept is autoreducibility, which was advanced as a tool for separating complexity classes in a notable paper by Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, and Leen Torenvliet. A set is autoreducible if there is a polynomial-time machine that on any input decides whether using as an oracle, but without querying itself. Other restrictions on are used to define the type of the reduction, leading to polynomial many-one (p-m) autoreducibility, truth-table (p-tt) autoreducibility, and so on. Here are some results in the new Nguyen-Selman paper, which is titled “Non-autoreducible Sets for NEXP”:
- is closed under complement if and only if every disjunctively-p-tt complete set for it is –p-tt autoreducible.
- There are polynomial Turing-complete sets for that are not p-tt autoreducible. Indeed for every there are complete sets for -query Turing reductions that have no autoreductions with fewer than queries.
- There are 3-query tt-complete sets for such that every 3-query tt-autoreduction must query non-polynomially shorter strings.
is a difficult class to work with—I’ve never gained a strong intuition for it—but currently important. The paper itself enunciates an anthem of structural complexity:
Proofs typically require intricate diagonalization arguments.
In view of Dexter Kozen’s argument that any proof of must intrinsically support a diagonalization, this may have a long reach. The point is that Alan has kept this long reach all the way through his eighth decade, and continues activities that promote the field for a new generation the way he did for mine.
Satish, Sargur Srihari, my wife Debbie and I, Mitsu, and Sharon
Does the ESY Conjecture hold, at least for a random oracle?
Dick and I salute Alan for a long friendship and happy productive future.
[fixed Cornell timings and identities of students]