Keeping a promise to structure the field of complexity

Alan Selman, my longtime friend and colleague, passed away last Friday, from the one illness that is most cruel for someone who has excelled by brainpower and effervescent joie de vivre alike.

Today, Dick and I join others in mourning and also in appreciation.

I last saw Alan with his wife Sharon in May 2019 at the dinner for the NP50 celebration of Steve Cook in Toronto. There were inklings of his affliction but nothing that kept him from engaging in dinner talk about how our field has progressed, about reunited friends, about the convivial atmosphere and culture on display during the celebration, and even my own goings-on with chess and quantum complexity and all our grown children. Alan was still going out to concerts last March until the pandemic stopped all that kind of activity.

I’ve known Alan in person for almost 40 years, starting a decade before he became my Chair for 6 years and colleague for 18 years more of them before his retirement and move to New Jersey. This was all through my graduate study at Oxford. It began at ICALP 1982 in Aarhus after my first year. During a December 1983 workshop at Brooklyn College he shared a problem with me whose story I told here. He visited me in Oxford in early 1986 accompanied by his son Jeffrey, whose eulogy in this past Sunday’s burial service was especially moving. Alan gave me other helps in 1985–86 that aided my “repatriation,” so to speak. My point is that he took great interest in builders of complexity theory even as students—Uwe Schöning noted that he visited him in 1982 while he was a student as well. My 2014 post on Alan’s retirement party expressed how this continued throughout.

P NE NP

As others have remarked, Alan’s cars had a license plate that declared P NE NP. Over a quarter century I regularly saw it in the parking lot serving Bell Hall, and after 2012, the same lot for our department’s new digs in Davis Hall. My colleague Sargur Srihari relates seeing someone approach Alan in the lot and say, “Yes, but can you prove it?”—adding that it was “probably the only thing in complexity that Alan couldn’t do.” An irony I will say here now is that the Dean of Engineering and Applied Sciences whom Alan worked with during much of his time as Chair, Mark Karwan, claims the opposite. It would have been fun to see a dueling license plate saying P EQ NP.

Synthesized via ACME license-plate composing app

Long followers of this blog know that Dick and I have embodied this duel between ourselves. Only recently has Dick swung toward , while some have moved the other way.

But what we think everyone would agree on is that we cannot point to any definite progress in the past dozen-plus years, at least not directly on the question. This struck me particularly from the Cook workshop, and this would have been the lead theme of a post on it, had I not been sprinting toward an effective June deadline to complete a major upgrade to my statistical chess model which I achieved two months later. No one attested real progress in comments to our P=NP status post a year ago. I wrote to Sharon two weeks ago that I wished I could tell Alan of progress but no.

Where Alan, Dick, I, and many of us are completely aligned is on these two points:

1. The importance of unwavering focus on P versus NP and other fundamental questions about computational problems, despite our field’s lack of scientific achievement in classifying them.
2. Emphasis on what our field has positively, scientifically, and perhaps surprisingly achieved, which is showing deep and crisp mathematical relations among thousands of diverse problems. These relations can be phrased not only in the common term reductions but in terms that arose in structural complexity, such as isomorphisms, (non-)adaptivity, parsinomiousness, and (in-)separability.

We put in the mouth of a fictional STOC 1500 keynote the position that relations between problems should be the field’s fundamental objects. There is incredible beauty in these objects, as was the theme of Lane Hemaspaandra’s tribute to Alan on his retirement surveying gems of Alan’s work, and it was my elation to be captivated by them beginning in my graduate years of the 1980s.

Elijah

Alan’s Hebrew name was Eliyahu, Elijah. In the Bible, Elijah is a traveling prophet: he not only goes from Zarephath to Beersheba but all the way south to Mount Sinai, where he is commanded to return all the way north to Damascus. The mission from Sinai is conveyed not in cloud and fire as with Moses, nor in wind or earthquake, but famously in a still small voice.

That was the kind of voice in which Alan during his many travels spread the love of complexity theory. I was glad to experience his kindness, good crisp advice, and also the giving of freedom to pursue things with zeal—a trait that Elijah had and recognized. I was not so fast to recognize good food and fine culture. I remember once when Alan was especially happy about securing tickets to see the 86-year-old legendary jazz violinist Stéphane Grappelli perform in Buffalo and I did not know who that was. I was, however, able to reply that I’d once seen Chet Baker live while standing in a small room in London. He and Sharon and my wife Debbie and I shared other musical interests. All of what I implied about whole-person education in my memorial for Peter Neumann applies to Alan. In Bell Hall we had only a mid-size seminar room for gatherings, yet Alan right away recognized the importance of making it like Oxford’s Mathematical Institute tea room—but with wine included—in weekly Friday afternoon “TGIF” gatherings open to faculty and graduate students, for which I did the shopping those mornings at Wegmans.

Elijah is also known as a keeper of promises. I won’t go into the gruesome biblical details here, but rather note that Alan shepherded a promise of a different kind: the notion of a promise problem, following on from his famous 1984 paper with Shimon Even and Yacov Yacobi. This is a structural complexity concept whose usage has grown, besides the original technical challenges which I recounted here. I’ve sometimes felt that wider uses have run risk of getting burned by inexactitudes, such as in the notion of promise-completeness. Alan’s exactness was one trait that made me feel at home.

Elijah also founds a school called the “sons of the prophets,” passing his mantle to Elisha before being taken up in a chariot of fire. It is not for me to say who might pick up Alan’s mantle in structural complexity. But many in his train have said wonderful things in tribute over the weekend, and I wish to pass along some of them, with quotes from those who have given permission or have already written in public, in particular as comments to Lance Fortnow’s tribute to Alan.

Some Tributes From Colleagues

The news was passed around our department in Buffalo. Our Chair, Chunming Qiao, mourned the loss of a great colleague, a former Chair, and a respected scholar. Sargur Srihari told the parking lot story above and and noted how Alan recruited a star to the department in the person of Jin-Yi Cai. Stuart Shapiro, who preceded and succeeded Alan as Chair, noted Alan’s higher personal standards for research and publishing. Russ Miller, writing earlier this month when we had news of Alan’s being in hospice care, hailed him as “a terrific person,” meeting the standard of a “true gentleman and scholar,” and hailed his communication skills with colleagues and the university administration alike. Jinhui Xu expressed thanks for Alan’s thoughtfulness and role as a mentor. I can say all this from my own experience. Many of us also took part in the earlier outpouring of affection, including photos and memories of Alan’s time in Buffalo, that was communicated to Sharon.

Mark Karwan adds, “Alan continued to win awards and accolades throughout my 12 years as Dean which ended in 2006. All of his professional accomplishments provided a great sense of pride and international recognition for UB. Alan was truly a senior leader and mentor for so many. He spoke to me as an advocate for his department and for the young rising faculty and the need to nourish and retain them. His wise counsel was always given in the most gentlemanly manner. When I picture Alan today, I see the twinkle in his eyes and his contagious joy of life. I only started working relatively recently with a colleague in our field of Operations Research on matters in complexity with implications to support P = NP. It would have been such fun to bring Alan into our conversations! We will all miss Alan and will always appreciate the great legacy he created here at UB.”

Jin-Yi, of course, is well known to all who knew Alan in the theory community and readers of this blog. He called Alan a great structural complexity theorist, and wrote in one of many e-mails I’ve been copied on: “Alan [was] a wonderful colleague of mine, and had a lifetime contribution to complexity theory that will certainly live on. He had a dry wit, enigmatic smile, and most of all, a truly kind heart. We will always remember him in our fond memory.”

Atri Rudra worked with Alan on many projects including organizing and securing funding for the Eastern Great Lakes (EaGL) Theory Workshops along with Bobby Kleinberg of Cornell. Here are two photos from the first one in 2008:

Composite from 2008 EaGL photo page; Kleinberg to Alan’s right and Atri (obscured) behind.

Atri writes, “I still remember being taken directly from the airport to Alan’s favorite restaurant, Trattoria Aroma, during my interview at Buffalo. I was a bit intimidated by Alan during the dinner but we bonded over the fact that we were both married to epidemiologists. After I joined Buffalo, Alan’s sage advice helped me throughout my tenure process. Alan was a giant in the department and having him in my corner did not hurt. [H]e had a wicked sense of humor as well.”

Mitsunori Ogihara succeeded Alan as Editor-in-Chief of the journal Theory of Computer Systems and blossomed from being a postdoc recruited by Alan at UB to being Chair of Computer Science at the University of Rochester in a few short years. The story of my taking Mitsu from the airport on a snowy night will be told another time. He is writing his own tribute to appear in the journal, from which I quote just a few words: “While being a scholar of uncanny vision and incredible ingenuity, Alan was a lovely human being. He was generous with his time for his students and colleagues, always willing to offer consultation and advice. The field of theoretical computer science has lost its giant. Alan is no longer here to lead us, but his legacy will live.”

Lane Hemaspaandra, Mitsu’s colleague at UR, writes: “Very briefly put, Alan’s research handiwork and vision is ingrained in the shape of the field. I was lucky enough to through his generosity know Alan across decades: we co-edited a book, wrote two research papers together, even wrote—Alan had a real love of writing and language—a note on writing in theoretical computer science, and had a long tradition of research seminars and theory days that brought together the University at Buffalo, RIT, and University of Rochester theory groups. Alan was also my wife’s wonderful postdoctoral advisor. And, throughout all that, and coexisting with Alan’s technical artistry and amazing taste in theory research, Alan’s love of and expertise in the ‘real’ world was quiet yet luminous. Alan loved the theater, and spoke warmly of his beloved Shaw Festival at Niagara-on-the-Lake. He loved and knew food; any restaurant commended by Alan was going to be an experience.”

Ashish Naik noted that he was Alan’s first student in Buffalo: “[I] still remember going to his office to ask if he would take me as a student, somewhat intimidated because of his stature in the field. Alan he put me at ease immediately with his sense of humor (I still remember the cartoon clippings on his office door) and his generosity. Despite a busy schedule as the Chair, Alan always had time for me — introducing me to the field, sharing interesting problems and his ideas, and teaching me how to write well and asking the right questions, skills that have stayed with me forever.”

D. Sivakumar was my student at the same time as Ashish, and began his own comment in Lance’s tribute by noting how Alan’s early work with Neil Jones on a logical characterization of nondeterministic exponential time was a precursor to Ron Fagin’s 1974 characterization of NP. He continued how at the end of his first year in Buffalo, “Alan encouraged us students to attend the Structures conference in Boston even though only one of us a theory-committed student. Alan drummed up some money to pay our registration, and we rented a car and stayed with friends in Boston. Structures’92 was magical for me—my first academic conference—everything about the atmosphere, the ideas, the people was fascinating and I decided to work in that field. All the work in my thesis (sparse sets, measure theory,…) were on topics I heard about for the first time at Structures’92—without Alan’s nudge, my life would likely have taken an entirely different trajectory. … Alan’s wit, dry humor, and his generosity are the things I’ll remember forever.”

Pavan Aduri was also Alan’s student in the 1990s and, speaking during a shiv’ah service with the family on Monday (via Zoom), noted Alan’s quest for simplicity in complexity theory. “Whenever I started to present a proof, Alan would ask, ‘Can you simplify the proof?’ ” Now at Iowa State, he recalled that he would frequently reach out to Alan for advice on various matters, even on what would be a more appropriate title for a research proposal. “Alan was always very generous with his time and advice.” Frederic Green related at the shiv’ah how Alan helped him migrate from physics to complexity and once reviewed every single step of four pages of notes on a complicated proof to optimize it for presentation. Steve Fenner told of Alan’s hosting him in Buffalo right after Steve’s PhD and putting him at ease with small talk about the permanently temporary quarters in Bell Hall. Steve Homer and his wife told of being travel partners exploring castles and flower markets, and the long gestation of the Homer-Selman textbook, Computability and Complexity Theory.

Harry Buhrman writes: “Alan has been an inspiration for me from the time I started working as a PhD student in complexity theory. My first encounter was his beautiful work on reductions and P-selective sets. I jokingly used to call them P-Selman-sets. I consider myself very lucky that he came over to my PhD defense in 1993 in Amsterdam. It was a joyous gathering.” I remember the photos Alan showed of that defence as well as Edith Hemaspaandra’s: grand pageantry on a scale I did not see even at Oxford, and led by Harry’s co-advisor Peter van Emde Boas, whose note in Lance’s tribute recalled the genesis of the “Structures” conferences in 1985–86 and the 1994 edition in Amsterdam and both hosting and visiting Alan and Sharon for dinners.

My retired colleague Mike Buckley wrote, “I taught with Alan at UB, and he taught me how to teach. Students sought him out until the day he left. He put as much into the undergrads as the PhDs. His presence at faculty meetings meant that no decision was made until he had his last comment. He was a giant in the field, but also the world’s nicest man. I kept in touch and we talked stereos and jazz. I miss him already.”

Arnold Rosenberg and Paul Spirakis hailed Alan as “a true pioneer and leader in the area of logic-based CS” and noted their long cooperation on the editorial board of the Theory of Computing Systems journal. Arnold continued: “He played vital roles in both research and education in CS. He approached every professional challenge with vision and unswerving devotion to the highest standards of our field. Our journal and our field have lost a great person.” Rod Downey included special thanks for Alan’s early support of parameterized complexity and the journal’s support, for instance in special issues.

Open Problems

Readers are welcome to place words of grace in comments; more may be added above as well.

Our embraces go to Sharon, to Jeffrey, to their daughter Heather—who also works in medicine—and to all the family.

[Cantor for the service was not Heather Wargo but Sandra Messinger Aguilar; some word fixes; linked license-plate app]