Commemorative Issue for Alan L. Selman

Alan L. Selman, a long-time editor and the Editor-in-Chief for 18 years, passed away on 22nd January 2021. Alan was a leader in computational complexity. He introduced various important research topics, including p-selective sets, natural self-reducible sets, promise problems, reducing search to decision problems, comparison of resource-bounded reducibilities, and multivalued nondeterministic functions. Alan also had done pioneering work in many areas of computational complexity theory, including sparse sets, relativization, average-case complexity, hierarchy theorems, structures of complete sets, and the complexity of multivalued functions.
In this special issue, we celebrate Alan’s life and commemorate his extraordinary contributions to the field. The topics of interest include but are not limited to: 

  • average-case complexity
  • circuit complexity
  • comparison of reducibilities
  • complexity theoretic characterizations of models
  • function complexity
  • hierarchy theorems
  • parameterized complexity
  • promise problems and disjoint NP-pairs
  • public-key cryptography
  • relativization
  • semi-feasible algorithms
  • sparse sets
  • structure of complete sets

We solicit contributions in the form of new research investigations, technical surveys, and memoirs. A technical contribution may include a section describing Alan’s influence on the authors, both on their academic careers and personal lives.

Responsible Editorial Board Members

Elvira Mayordomo, Universidad de Zaragoza,
Mitsu Ogihara, University of Miami,
Atri Rudra, University at Buffalo,

Important Dates

Deadline for Submissions: 31st July 2021
Deadline for reviews:            30th October 2021
Deadline for revised version: 30th November 2021
Deadline for second reviews: 31st January 2022
Final decision:                       15th February 2022

Submission Guidelines

Authors should follow the formatting and submission instructions for TOCS at

During the first submission step in Editorial Manager select 'Original article' as the article type. In further steps you should confirm that your submission belongs to this special issue by choosing the special issue title from the drop-down menu.