Alan L. Selman

According to our database1, Alan L. Selman authored at least 95 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 
Other 

Links

Homepage:

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.
TOCT, 2016

A thirty Year old conjecture about promise problems.
Computational Complexity, 2016

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

Non-autoreducible Sets for NEXP.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

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

2013
Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 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

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

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

The Complexity of Unions of Disjoint Sets.
Proceedings of the STACS 2007, 2007

Non-mitotic Sets.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

The Informational Content of Canonical Disjoint NP-Pairs.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

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

Redundancy in Complete Sets.
Proceedings of the STACS 2006, 2006

Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems.
Proceedings of the Theoretical Computer Science, 2006

2005
Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems
Electronic Colloquium on Computational Complexity (ECCC), 2005

Redundancy in Complete Sets
Electronic Colloquium on Computational Complexity (ECCC), 2005

Autoreducibility, Mitoticity, and Immunity
Electronic Colloquium on Computational Complexity (ECCC), 2005

Canonical Disjoint NP-Pairs of Propositional Proof Systems.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Autoreducibility, Mitoticity, and Immunity.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004
Canonical Disjoint NP-Pairs of Propositional Proof Systems
Electronic Colloquium on Computational Complexity (ECCC), 2004

Properties of NP-Complete Sets
Electronic Colloquium on Computational Complexity (ECCC), 2004

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 2004

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

Reductions between Disjoint NP-Pairs.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Properties of NP-Complete Sets.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003
Reductions between Disjoint NP-Pairs
Electronic Colloquium on Computational Complexity (ECCC), 2003

Disjoint NP-Pairs
Electronic Colloquium on Computational Complexity (ECCC), 2003

Disjoint NP-Pairs.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Bi-Immunity Separates Strong NP-Completeness Notions
Electronic Colloquium on Computational Complexity (ECCC), 2002

Bi-Immunity Separates Strong NP-Completeness Notions.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

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

Editorial Statement.
Theory Comput. Syst., 2001

Separation of NP-completeness Notions
Electronic Colloquium on Computational Complexity (ECCC), 2001

The history and contribution of theoretical computer science.
Advances in Computers, 2001

Separation of NP-Completeness Notions.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

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

1999
Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets.
Computational Complexity, 1999

Distributionally-Hard Languages.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 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
P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility.
J. Comput. Syst. Sci., 1996

Computing Solutions Uniquely Collapses the Polynomial Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 1996

Fine Separation of Average Time Complexity Classes.
Proceedings of the STACS 96, 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

Complements of Multivalued Functions.
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
Electronic Colloquium on Computational Complexity (ECCC), 1995

Wide Area Technical Report Service: Technical Reports Online.
Commun. ACM, 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

Computing Solutions Uniquely collapses the Polynomial Hierarchy.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993
Complexity Classes for Partial Functions.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 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.
Mathematical Systems Theory, 1992

1991
Complexity Classes for Partial Functions.
Bulletin of the EATCS, 1991

1990
Hard Promise Problems and Nonuniform Complexity.
Proceedings of the STACS 90, 1990

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

1989
Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

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
Information and Control, May, 1984

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

Characterizations of Reduction Classes Modulo Oracle Conditions.
Mathematical Systems 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
Information and 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.
Proceedings of the Automata, 1979

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

1977
Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.
Mathematical Systems Theory, 1977

1976
A Second Step toward the Polynomial Hierarchy
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

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...