Alan L. Selman

Affiliations:
  • University at Buffalo, USA


According to our database1, Alan L. Selman authored at least 83 papers between 1972 and 2017.

Collaborative distances:

Awards

ACM Fellow

ACM Fellow 1998, "Throughout his career Alan L. Selman has been an influential contributor to computational complexity theory and a dedicated professional within the academic comuter science community.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2017
50 Years of TOCS.
Theory Comput. Syst., 2017

Introduction to Autoreducibility and Mitoticity.
Proceedings of the Computability and Complexity, 2017

2016
Structural Properties of Nonautoreducible Sets.
ACM Trans. Comput. Theory, 2016

A thirty Year old conjecture about promise problems.
Comput. Complex., 2016

2014
Disjoint NP-Pairs and Propositional Proof Systems.
SIGACT News, 2014

Turing and the development of computational complexity.
Proceedings of the Turing's Legacy: Developments from Turing's Ideas in Logic, 2014

2013
Non-autoreducible Sets for NEXP.
Electron. Colloquium Comput. Complex., 2013

Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions.
Electron. Colloquium Comput. Complex., 2013

2012
A Thirty Year Old Conjecture about Promise Problems.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Foreword.
J. Comput. Syst. Sci., 2011

Computability and Complexity Theory, Second Edition.
Texts in Computer Science, Springer, ISBN: 978-1-4614-0682-2, 2011

2009
Non-mitotic sets.
Theor. Comput. Sci., 2009

2008
Splitting NP-Complete Sets.
SIAM J. Comput., 2008

The complexity of unions of disjoint sets.
J. Comput. Syst. Sci., 2008

2007
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy.
Theor. Comput. Sci., 2007

Canonical disjoint NP-pairs of propositional proof systems.
Theor. Comput. Sci., 2007

Autoreducibility, mitoticity, and immunity.
J. Comput. Syst. Sci., 2007

The Informational Content of Canonical Disjoint NP-Pairs.
Electron. Colloquium Comput. Complex., 2007

2006
Properties of NP-Complete Sets.
SIAM J. Comput., 2006

Mitosis in Computational Complexity.
Proceedings of the Theory and Applications of Models of Computation, 2006

2005
Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems
Electron. Colloquium Comput. Complex., 2005

Redundancy in Complete Sets
Electron. Colloquium Comput. Complex., 2005

2004
Disjoint NP-Pairs.
SIAM J. Comput., 2004

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy
Electron. Colloquium Comput. Complex., 2004

Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003
Reductions between Disjoint NP-Pairs
Electron. Colloquium Comput. Complex., 2003

2002
Bi-Immunity Separates Strong NP-Completeness Notions
Electron. Colloquium Comput. Complex., 2002

2001
Computability and Complexity Theory.
Texts in Computer Science, Springer, ISBN: 978-1-4757-3544-4, 2001

Separation of NP-Completeness Notions.
SIAM J. Comput., 2001

Editorial Statement.
Theory Comput. Syst., 2001

Distributionally Hard Languages.
Theory Comput. Syst., 2001

The history and contribution of theoretical computer science.
Adv. Comput., 2001

2000
Complete distributional problems, hard languages, and resource-bounded measure.
Theor. Comput. Sci., 2000

1999
Fine Separation of Average-Time Complexity Classes.
SIAM J. Comput., 1999

Complements of Multivalued Functions.
Chic. J. Theor. Comput. Sci., 1999

Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets.
Comput. Complex., 1999

1998
A Hierarchy Based on Output Multiplicity.
Theor. Comput. Sci., 1998

Writing and editing complexity theory: tales and tools.
SIGACT News, 1998

1997
Strategic directions in research in theory of computing.
SIGACT News, 1997

Oracles that Compute Values.
SIAM J. Comput., 1997

1996
Computing Solutions Uniquely Collapses the Polynomial Hierarchy.
SIAM J. Comput., 1996

P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility.
J. Comput. Syst. Sci., 1996

Much Ado about Functions.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
Nondeterministically Selective Sets.
Int. J. Found. Comput. Sci., 1995

Average Time Complexity Classes
Electron. Colloquium Comput. Complex., 1995

1994
Wide area technical report service - technical reports online.
SIGACT News, 1994

A Taxonomy of Complexity Classes of Functions.
J. Comput. Syst. Sci., 1994

1993
Complexity Classes for Partial Functions.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Hard Promise Problems and Nonuniform Complexity.
Theor. Comput. Sci., 1993

On Using Oracles That Compute Values.
Proceedings of the STACS 93, 1993

Selectivity.
Proceedings of the Computing and Information, 1993

P-Selective Sets, and Reducing Search to Decision vs. Self-Reducability.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
A Survey of One-Way Functions in Complexity Theory.
Math. Syst. Theory, 1992

Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography.
J. Comput. Syst. Sci., 1992

1991
Complexity Classes for Partial Functions.
Bull. EATCS, 1991

1990
One-Way Functions in Complexity Theory.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1988
Promise Problems Complete for Complexity Classes
Inf. Comput., August, 1988

Natural Self-Reducible Sets.
SIAM J. Comput., 1988

Complexity Measures for Public-Key Cryptosystems.
SIAM J. Comput., 1988

1987
A Hierarchy Theorem for Almost Everywhere Complex Sets With Application to Polynomial Complexity Degrees.
Proceedings of the STACS 87, 1987

1986
Relativizing complexity classes with sparse oracles.
J. ACM, 1986

1985
Hard-Core Theorems for Complexity Classes
J. ACM, January, 1985

Qualitative Relativizations of Complexity Classes.
J. Comput. Syst. Sci., 1985

1984
The Complexity of Promise Problems with Applications to Public-Key Cryptography
Inf. Control., May, 1984

Quantitative Relativizations of Complexity Classes.
SIAM J. Comput., 1984

Characterizations of Reduction Classes Modulo Oracle Conditions.
Math. Syst. Theory, 1984

Complexity Measures for Public-Key Cryptosystems (Preliminary Report)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Sparse Oracles and Uniform Complexity Classes
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Positive Relativizations of Complexity Classes.
SIAM J. Comput., 1983

Controlled relativizations of P and NP.
Proceedings of the Theoretical Computer Science, 1983

1982
Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity
Inf. Control., January, 1982

Reductions on NP and P-Selective Sets.
Theor. Comput. Sci., 1982

The Complexity of Promise Problems.
Proceedings of the Automata, 1982

1981
Some Observations on NP, Real Numbers and P-Selective Sets.
J. Comput. Syst. Sci., 1981

1979
A Second Step Toward the Polynomial Hierarchy.
Theor. Comput. Sci., 1979

P-selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP.
Math. Syst. Theory, 1979

1978
Polynomial Time Enumeration Reducibility.
SIAM J. Comput., 1978

1977
Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.
Math. Syst. Theory, 1977

1975
A Comparison of Polynomial Time Reducibilities.
Theor. Comput. Sci., 1975

1974
Turing Machines and the Spectra of First-Order Formulas.
J. Symb. Log., 1974

Comparisons of Polynomial-Time Reducibilities
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1972
Turing Machines and the Spectra of First-Order Formulas with Equality
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972


  Loading...