Skip to content

NEXP and the Next Generation

May 13, 2014


Saluting Alan Selman upon the occasion of his retirement

AlanRet
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.


AlanWholeRoom

The Party

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 {R} admit a function {f} such that whenever {R(x,y)} holds, {R(x,f(x))} holds, and {f} 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:


AlanStudentsLaneEdith


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.


AlanSharonSatishAidong


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 {\mathsf{NP}}-hardness unless {\mathsf{NP = co}\text{-}\mathsf{NP}}, remains elusive.

NEXP

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, {\mathsf{NEXP}}) from non-uniform {\mathsf{ACC^0}}. This theorem leverages combinatorial results, but in itself is a careful application of structural ideas. With {\mathsf{EXP}} 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 {A} is autoreducible if there is a polynomial-time machine {M} that on any input {x} decides whether {x \in A} using {A} as an oracle, but without querying {x} itself. Other restrictions on {M} 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”:

Theorem 1

  1. {\mathsf{NEXP}} is closed under complement if and only if every disjunctively-p-tt complete set for it is {\mathsf{NOR}}p-tt autoreducible.

  2. There are polynomial Turing-complete sets for {\mathsf{NEXP}} that are not p-tt autoreducible. Indeed for every {s} there are complete sets for {s}-query Turing reductions that have no autoreductions with fewer than {2^s - 1} queries.

  3. There are 3-query tt-complete sets for {\mathsf{NEXP}} such that every 3-query tt-autoreduction must query non-polynomially shorter strings.

{\mathsf{NEXP}} 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 {\mathsf{P \neq NP}} 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.

SharonKenDebMitsuHariSatish
Satish, Sargur Srihari, my wife Debbie and I, Mitsu, and Sharon

Open Problems

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]

5 Comments leave one →
  1. May 13, 2014 10:57 pm

    Hi Ken, Great article on Alan. I wish I could be there in person to congratulate Alan for his great influence to a whole generation of complexity theorists, myself included. (But unfortunately, as I told Alan, due to a previous commitment made before I received the notice of this celebration, I couldn’t be there in person.) Alan’s notion of p-selective sets is really a gem. For example, one can see essentially this notion of p-selective sets is behind the particularly short and beautiful proof of Mahaney’s theorem by Ogihara and Watanabe. I like this proof very much. This theorem says: If NP has a sparse hard set under Karp reduction, then P=NP. This has the generalization to the Ogihara-Watanabe Theorem with p-time btt-reduction replacing Karp reduction. Of course relaxing to the Cook reduction, you have the famous Karp-Lipton Theorem, which can be stated as: If NP has a sparse hard set under Cook reduction, then the polynomial-time hierarchy collapses to its second level.

    One small correction if I may: I don’t think you (Ken) and I intersected at Cornell (I had left Cornell during 1986). Of course you (Ken), I and Alan were together at Buffalo for many years. It was a very productive period in complexity research, e.g., the proof of the Hartmanis Conjectures. All this under the leadership of Alan for the western NY complexity theory research. So, many thanks, Alan, and happy retirement! (I am sure you will still be very active in research during “retirement”.)

    • May 13, 2014 11:05 pm

      Thanks, Jin-Yi. I’m probably remembering one or more of your visits while Gabi was still there—?

  2. May 14, 2014 11:20 am

    Say hi to Alan for me

    Dick from the beach

  3. May 14, 2014 3:37 pm

    I have fond memories of the Buffalo – Rochester Complexity seminar in the mid 90s (1992-1996).

    I remember the following people who participated regularly for at least some part of this period: Alan Selman, Jin-yi Cai, Ken Regan, Lane Hemaspaandra, Joel Seiferas, Mitsu Ogihara, Osamu Watanabe, and students Ashish Naik, D. Sivakumar, Ioan Macarie, Gabriel istrate, Robert Szelepsczenyi, Marius Zimand (me).

    Many thanks to Alan for being a catalyst of Complexity research in upstate NY and elsewhere.

    Marius Zimand

  4. May 14, 2014 4:14 pm

    Congratulations on this milestone, Alan! I look forward to seeing even more papers from you, now that departmental and university committee meetings are things of the past! Enjoy!

    — Eric

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s