UB Logo CSE Logo
Alan Selman, Professor Emeritus

In Memoriam

April 2, 1941—January 22, 2021

Alan was a loving husband, father and grandfather. He was very proud of the accomplishments of his two children, Jeffrey and Heather, and nurtured them by example. Likewise, he encouraged me in my academic pursuits. And he always had room in his heart for his five grandchildren, Sarah, Elana, Benjamin, Rebecca, and Eliza. We met in college on April Fool’s Day almost 61 years ago, a day before his 19th birthday and 3 days before my 17th birthday.

He was a scholar, having received his PhD in mathematics, but soon transitioning into computer science at the dawn of that field. Over his 40+ year career he helped to shape the field of theoretical computer science (he always said it was really mathematics), mentoring students, post doctoral fellows, younger faculty and colleagues with kindness and grace. His awards include a Fulbright award, Humboldt award, an award from the Japan Society for the Promotion of Science, and the Chancellor’s Award for Excellence in Scholarship and Creative Activities from the University at Buffalo, where he spent the final 24 years of his career. He was an ACM Fellow and received the ACM-SIGACT Distinguished Service Prize for co-founding the Conference on Computational Complexity (formerly known as Structures in Complexity Theory) and serving as its first Chair. I still remember the week he and Steve Mahaney spent sitting in my living room writing the grant to fund the first meeting, which took place in 1986. The conference has taken place every year since then, either in the US or another country – it was decided many years ago that since the attendees were international it should take place internationally. Alan also was an editor on several journals, and served as Editor-in-Chief of Theory of Computing Systems (TOCS) for 18 years (the last 4+ years after he retired from his teaching position at UB.

Alan loved math, but he also loved music and art. That could include collecting, museums, concerts, opera, theater, ballet and the like. His college education was broad enough (and, of course, his grades were good enough) in the liberal arts to earn him membership in Phi Beta Kappa.

Alan also loved to travel and we traveled many places for his work, to conferences and the like. But we always took some extra time wherever we went for exploring on our own. His first big trip was a few months after we met. His father helped him get an amazing summer job between college semesters. He worked as a merchant marine (yes, he had merchant marine papers) and sailed on a ship from New Orleans and Houston across the Atlantic to Spain and Le Havre. I remember him telling me how he took a bus from the latter to Paris to spend a few hours in that city, where he bought a bottle of champagne and drank it on the way back to Le Havre. On the ship he had mundane tasks like chipping rust. But on nights when he had night watch, he enjoyed the expansive night sky and could be found writing poetry on the deck.

—Sharon Selman, wife and soul mate

Portrait of Alan Selman
Alan L. Selman, Professor Emeritus

Computability and Complexity Theory, by Steven Homer and Alan L. Selman, Springer Verlag NY, 2001

Report of an NSF-Sponsored Workshop on Research in Theoretical Computer Science, 1999

Teaching Activities

Activities

Professor Selman is a Fellow of the ACM, recipient of a Humboldt research award (2005), an Invitation Fellowship for research in Japan from the Japan Society for the Promotion of Science (1996), and a Fulbright scholar (1981).
Curriculum Vitae: (pdf)

Recent Papers

  1. C. Glasser, A. Selman, and L. Zhang. The Informational Content of Canonical Disjoint NP-Pairs. (pdf) 13th Annual International Computing and Combinatorics Conference, Banff, Canada, July 2007.
  2. C. Glasser, A. Pavan, A. Selman, and L. Zhang. Mitosis in Computational Complexity. (pdf) Text of my plenary lecture at the Third International Conference, Theory and Applications of Models of Computation, Beijing, May, 2006.
  3. C. Glasser, A. Selman, S. Travers, and K. Wagner. The Complexity of Unions of Disjoint Sets. (pdf)

  4. C. Glasser, A. Selman, S. Travers, and L. Zhang. Non-Mitotic Sets. (pdf)

  5. C. Glasser, A. Selman, L. Zhang. Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems. (ps) (pdf) In Theoretical Computer Science, Essays in Memory of Shimon Even, eds. O. Goldreich, A. Rosenberg, and A. Selman, LNCS 3895, Springer, 2006.

  6. C. Glasser, A. Pavan, A. Selman, and L. Zhang. Redundancy in Complete Sets. (ps) (pdf) 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 2006.

  7. C. Glasser, M. Ogihara, A. Pavan, A. Selman, and L. Zhang. Autoreducibility, Mitoticity, and Immunity. (ps) (pdf) 30th International Symposium on Mathematical Foundations of Computer Science, Gdansk, Poland, 2005.

  8. C. Glasser, A. Selman, and L. Zhang. Canonical Disjoint NP-Pairs of Propositional Proof Systems. (ps) (pdf) 30th International Symposium on Mathematical Foundations of Computer Science, Gdansk, Poland, 2005.

  9. C. Glasser, A. Pavan, A. Selman, and S. Sengupta. Properties of NP-Complete Sets. (ps) (pdf) 19th IEEE Conference on Computational Complexity, Amherst, MA, June, 2004.

  10. A. Selman and S. Sengupta. Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy. (ps) (pdf) 19th IEEE Conference on Computational Complexity, Amherst, MA, June, 2004.

  11. C. Glasser, A. Selman, and S. Sengupta. Reductions between Disjoint NP-Pairs. (ps) (pdf) 19th IEEE Conference on Computational Complexity, Amherst, MA, June, 2004.

  12. C. Glasser, A. Selman, S. Sengupta, and L. Zhang. Disjoint NP-Pairs. (ps) (pdf) 18th IEEE Conference on Computational Complexity, Aarhus, Denmark, July, 2003.

  13. A. Pavan and A. Selman. Bi-Immunity Separates Strong NP-completeness Notions. (ps) (pdf) 19th International Symposium on Theoretical Aspects of Computer Science, Antibes Juan-les-Pins, France, March, 2002.

  14. A. Pavan and A. Selman. Separaton of NP-completeness notions. (ps) (pdf) SIAM Journal on Computing, 31(3):906--918, 2002.

  15. J. Savage, A. Selman, and C. Smith. History and Contributions of Theoretical Computer Science. (ps) (pdf) In Advances in Computing, ed. M. Zelkowitz, Academic Press, v. 55, 2001.

  16. L. Fortnow, A. Pavan, and A. Selman. Distributionally hard languages. Theory of Computing Systems, 34(3):245--263, 2001.

  17. A. Selman. Much ado about functions. (ps) (pdf) Text of invited address given at the Eleventh IEEE Conference on Computational Complexity, May, 1996.

  18. A. Naik, J. Rogers, J. Royer, and A. Selman. A hierarchy based on output multiplicity. (ps) (pdf) Theoretical Computer Science, 207(1):131--157, 1998.

  19. A. Pavan and A. Selman. Complete distributional problems, hard languages, and resource-bounded measure. (ps) (pdf) Theoretical Computer Science, 234(1--2):273--286, 2000.

  20. A. Naik and A. Selman. Adaptive versus nonadaptive queries to NP and p-selective sets. (ps) (pdf) Computational Complexity, 8(2):171--189, 1999.

  21. J-Y. Cai and A. Selman. Fine separation of average time complexity classes. SIAM Journal on Computing, 28(4):1310--1325, 1999.

  22. S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, and H. Vollmer. Complements of multivalued functions. Chicago Journal of Theoretical Computer Science, March 19, 1999.

ACM Digital Library

ACM DL Author-ize serviceWriting and editing complexity theory: tales and tools
Lane A. Hemaspaandra, Alan L. Selman
ACM SIGACT News, 1998
ACM DL Author-ize serviceStrategic directions in research in theory of computing
Anne Condon, Faith Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys
ACM SIGACT News, 1997
ACM DL Author-ize serviceWide Area Technical Report Service: technical reports online
James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman
Communications of the ACM, 1995
ACM DL Author-ize serviceWide area technical report serviceEUR"technical reports online
Jim French, Edward Fox, Kurt Maly, Alan L. Selman
ACM SIGACT News, 1994
ACM DL Author-ize serviceRelativizing complexity classes with sparse oracles
Timothy J. Long, Alan L. Selman
Journal of the ACM (JACM), 1986
ACM DL Author-ize serviceHard-core theorems for complexity classes
Shimon Even, Alan L. Selmen, Yacov Yacobi
Journal of the ACM (JACM), 1985
ACM DL Author-ize serviceComparison of polynomial-time reducibilities
Richard Ladner, Nancy Lynch, Alan Selman
STOC '74 Proceedings of the sixth annual ACM symposium on Theory of computing, 1974
ACM DL Author-ize serviceTuring machines and the spectra of first-order formulas with equality
Neil D. Jones, Alan L. Selman
STOC '72 Proceedings of the fourth annual ACM symposium on Theory of computing, 1972

Personal

Photos from my trip to Japan, April 1996 (taken by Professor Namiki,TUAT, with his digital camera). Professor Nakamori, TUAT, was my host.

Grandchildren


Send comments: webmaster@@cse.Buffalo.EDU