 |
| From a 1994 Dagstuhl Workshop. Selman is the one wearing a cap. |
Selman was a good colleague and a friend. I hosted his sabbatical at the University of Chicago in 1998 which produced a paper with Selman's student and my later postdoc Pavan Aduri. In Spring of 1999 Selman ran a NSF workshop in Chicago on Challenges for Theory of Computing.
In a desire to create a community of complexity theorists and foster publications of their results, Selman led the efforts to establish the Structure in Complexity Theory conference, first held in 1986 in Berkeley, California. As a student in Berkeley I attended that meeting and the next twenty-five. The conference would join the IEEE in 1987, in 1996 renamed the IEEE Conference and Computational Complexity and in 2015 drop from the IEEE to become the Computational Complexity Conference, still going strong. Alan served as the first conference chair and as PC co-chair of the first meeting.
For all his service for the field, Selman received the ACM SIGACT Distinguished Service Award in 2002.
Selman joined University at Buffalo in 1990 to serve six years as department chair and then as a professor until he retired in 2014. Lane Hemaspaandra wrote a highly recommended appreciation for Selman and his research in honor of his retirement where he mentions some of Selman's research programs, including his seminal work on P-Selective sets, non-deterministic functions and his work with Joachim Grollman on one-way functions. Selman came down hard on anyone who got the wrong number of l's in Grollman, so we would often joking cite it as Grollman and Sellman or just Grollman et Al.
In my favorite Selman paper, in work with Hemaspaandra, Ashish Naik and Mitsu Ogihara, looks at witness reduction. If there is a set A in P such that for all satisfiable formula φ there is a unique satisfying assignment a of φ such that (φ,a) is in A then the polynomial-time hierarchy collapses. The more general question of whether NP=UP implies the polynomial-time hierarchy collapses remains open.
Also Selman's paper with Steve Homer giving an oracle where Σ2P-complete sets were isomorphic was instrumental to my own work on the isomorphism conjecture.
Bill wanted me to mention the Selman paper that most influenced him. Selman and Theodore Baker and gave the first oracle separating the second level of the polynomial-time hierarchy in 1979. It would take Yao and Håstad over five more years to get the whole hierarchy infinite relative to an oracle. The Baker-Selman proof could easily extend to show that AM games did not sit in Σ2P, a bit surprising as MA is in Σ2P.
In addition to his research, Selman wrote an introductory theory textbook with Homer as well as editor and co-editor of two editions of Complexity Theory Retrospective.
It would be no exaggeration to say the field of computational complexity and my own research within it would have been much different without Alan.
Alan drove a car with a "P NE NP" license plate. One day someone came up to him in a parking lot and said "Yes, but can you prove it?" Possibly the one thing in complexity he couldn't do.
Lance has a nice summary of Alan's research and external service so I wanted to focus on Alan's mentorship. I joined Buffalo in 2007 and benefited immensely from Alan's mentorship.
ReplyDeleteI still remember being taken directly from the airport to Alan's favorite Italian restaurant 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 :-) Oh, and it turns out he had a wicked sense of humor as well.
Even though we were not in regular touch after he retired in 2014, I still (and now sadly will) miss his sage advice and wit in handling tricky situations.
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 udergrads 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.
ReplyDelete...Mike Buckley, UB
I was Alan’s first student at Buffalo, and 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.
ReplyDeleteI have fond memories of the Buffalo-Rochester theory meetings that Alan started with Lane and Edith Hemspaandra and Mitsu Ogihara. During those drives, Alan provided valuable tips on driving, his technique of parallel parking is something I still use today. He also loved showing off the awesome acceleration of his Saab on I-90.
I feel blessed to have known Alan as my advisor, mentor, and as a friend.
Driving with Alan on his Saab was fun.
DeleteI have known Alan Selman for a long period. The earliest evidence I could find in my picture collection dates from 1981 when we both participated in the proto-complexity meeting organized in Purdue.
ReplyDeleteAlan invited me to join in the preparation of what became the Structure in Complexity series in 1985. I remember that we had the PC meeting for the first conference in the winter of 1986 at the Chicago Airport. Afterwards he invited me for a visit to Ames Iowa where he was working at that time. I stayed at his home surprising the family by my desire to expose myself to the -30 outside temperature in order to feel what it means to be very cold.
For years I remained active in the Structure events; we organized the 1994 session in Amsterdam.
During the early 1990-ies we had a series of meetings in a cooperation between Amsterdam, Boston and Buffalo on Complexity theory.
Alan and Sharon have visited our place as well (I remember walking together on the beach), and in later years we used to have joint diners when we met at conferences together with our wifes.
It is sad to learn that he has left us.
I don't know why the sender was lost on this remark.
DeleteFor good order: it was written by Peter van Emde Boas.
So many Alan memories... but first a technical result, one of Alan's least well-known results (doesn't feature, for example, in Lane's lovely "Beautiful Structures" article).
ReplyDeleteIn STOC 1972, Alan and Neil Jones proved that the spectra of first-order formula coincides with the complexity class NE (= 2^{O(n)} time), see here: https://www.jstor.org/stable/2272354?seq=1. This was a "binary encoding" precursor to Ron Fagin's famous 1974 paper that showed that the "generalized spectra" of first-order formulas coincides with NP (see PDF of Fagin's paper here: https://researcher.watson.ibm.com/researcher/files/us-fagin/genspec.pdf). The latter result is widely considered the birth of finite model theory.
Alan also played a major part in my deciding to work on (structural) complexity theory.
In my second semester of grad school, I (boldly and somewhat foolishly) signed up for a graduate seminar in complexity theory that Alan led. There were 4-5 grad students in it, and one of Alan's goals was to understand the body of work on interactive proofs, so we studied the classics (in fact, the PCP theorem happened as we were wrapping up the term).
At the end of that term, 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!
It wasn't until a couple years after graduation that I managed to write a paper on a quintessentially-Alan concept in structural complexity: p-selectivity. Here I was so happy to connect this "Alan topic" with things I learned for the first time in that Spring 1992 seminar on complexity theory (the use of low-degree polynomials, Madhu's fabulous list-decoding algorithm...). Alan was very generous with his praise when I presented this work at CCC'98 in Buffalo.
Alan's wit, dry humor, and his generosity are the things I'll remember forever. RIP Alan Selman.
Thank you Lance and other commenters for bringing back these memories of Alan Selman and a smile on my face when reading them. Alan was a great teacher and a dear friend. We met him and Sharon way back in 1990 in France (at least, in my memory, but memories place back good relationships further back more often). He, unknowingly, played a big part in my PhD thesis with his papers and later in further publications on P-selective sets, which he brought to complexity theory. Later, we had more extensive meetings with quite a large group here in Amsterdam and back in Buffalo where he inspired us and many students. Back in his beautiful house, we had deep conversations on science and the situation in the world from which I learned a lot. Looking back, our meetings were not frequent, but made a deep impression on me, thus seeming more frequent than they were.
ReplyDeleteI owe a big debt of gratitude to Alan Selman. The world has lost a great mind and a wonderful teacher.