Alan L. Selman

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2017

50 Years of TOCS.

Alan L. Selman, Arnold L. Rosenberg

Theory Comput. Syst., 2017

Introduction to Autoreducibility and Mitoticity.

Christian Glaßer, Dung T. Nguyen, Alan L. Selman, Maximilian Witek

Proceedings of the Computability and Complexity, 2017

2016

Structural Properties of Nonautoreducible Sets.

Dung T. Nguyen, Alan L. Selman

ACM Trans. Comput. Theory, 2016

A thirty Year old conjecture about promise problems.

Andrew Hughes, Debasis Mandal, Aduri Pavan, Nathan Russell, Alan L. Selman

Comput. Complex., 2016

2014

Disjoint NP-Pairs and Propositional Proof Systems.

Christian Glaßer, Andrew Hughes, Alan L. Selman, Nils Wisiol

SIGACT News, 2014

Non-autoreducible Sets for NEXP.

Dung T. Nguyen, Alan L. Selman

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

Turing and the development of computational complexity.

Steven Homer, Alan L. Selman

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.

Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

A Thirty Year Old Conjecture about Promise Problems.

Andrew Hughes, Aduri Pavan, Nathan Russell, Alan L. Selman

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Foreword.

Jin-yi Cai, Alan L. Selman

J. Comput. Syst. Sci., 2011

Computability and Complexity Theory, Second Edition.

Steven Homer, Alan L. Selman

Texts in Computer Science, Springer, ISBN: 978-1-4614-0682-2, 2011

2008

Splitting NP-Complete Sets.

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang

SIAM J. Comput., 2008

2007

Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy.

Aduri Pavan, Alan L. Selman, Samik Sengupta, N. V. Vinodchandran

Theor. Comput. Sci., 2007

The Complexity of Unions of Disjoint Sets.

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner

Proceedings of the STACS 2007, 2007

Non-mitotic Sets.

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

The Informational Content of Canonical Disjoint NP-Pairs.

Christian Glaßer, Alan L. Selman, Liyu Zhang

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Mitosis in Computational Complexity.

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang

Proceedings of the Theory and Applications of Models of Computation, 2006

Redundancy in Complete Sets.

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang

Proceedings of the STACS 2006, 2006

Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems.

Christian Glaßer, Alan L. Selman, Liyu Zhang

Proceedings of the Theoretical Computer Science, 2006

2005

Canonical Disjoint NP-Pairs of Propositional Proof Systems.

Christian Glaßer, Alan L. Selman, Liyu Zhang

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Autoreducibility, Mitoticity, and Immunity.

Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Alan L. Selman, Samik Sengupta

Electron. Colloquium Comput. Complex., 2004

Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy.

Alan L. Selman, Samik Sengupta

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Reductions between Disjoint NP-Pairs.

Christian Glaßer, Alan L. Selman, Samik Sengupta

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Properties of NP-Complete Sets.

Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Disjoint NP-Pairs.

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Bi-Immunity Separates Strong NP-Completeness Notions.

Aduri Pavan, Alan L. Selman

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001

Computability and Complexity Theory.

Steven Homer, Alan L. Selman

Texts in Computer Science, Springer, ISBN: 978-1-4757-3544-4, 2001

Editorial Statement.

Alan L. Selman

Theory Comput. Syst., 2001

The history and contribution of theoretical computer science.

John E. Savage, Alan L. Selman, Carl Smith

Adv. Comput., 2001

Separation of NP-Completeness Notions.

Aduri Pavan, Alan L. Selman

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Complete distributional problems, hard languages, and resource-bounded measure.

Aduri Pavan, Alan L. Selman

Theor. Comput. Sci., 2000

1999

Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets.

Ashish V. Naik, Alan L. Selman

Comput. Complex., 1999

Distributionally-Hard Languages.

Lance Fortnow, Aduri Pavan, Alan L. Selman

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

A Hierarchy Based on Output Multiplicity.

Ashish V. Naik, John D. Rogers, James S. Royer, Alan L. Selman

Theor. Comput. Sci., 1998

Writing and editing complexity theory: tales and tools.

Lane A. Hemaspaandra, Alan L. Selman

SIGACT News, 1998

1997

Strategic directions in research in theory of computing.

Anne Condon, Faith E. 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

SIGACT News, 1997

Oracles that Compute Values.

Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman

SIAM J. Comput., 1997

1996

P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility.

Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman

J. Comput. Syst. Sci., 1996

Fine Separation of Average Time Complexity Classes.

Jin-yi Cai, Alan L. Selman

Proceedings of the STACS 96, 1996

Much Ado about Functions.

Alan L. Selman

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.

Ashish V. Naik, Alan L. Selman

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Complements of Multivalued Functions.

Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Nondeterministically Selective Sets.

Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang

Int. J. Found. Comput. Sci., 1995

Average Time Complexity Classes

Jin-yi Cai, Alan L. Selman

Electron. Colloquium Comput. Complex., 1995

1994

Wide area technical report service - technical reports online.

James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman

SIGACT News, 1994

A Taxonomy of Complexity Classes of Functions.

Alan L. Selman

J. Comput. Syst. Sci., 1994

Computing Solutions Uniquely collapses the Polynomial Hierarchy.

Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993

Complexity Classes for Partial Functions.

Alan L. Selman

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On Using Oracles That Compute Values.

Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman

Proceedings of the STACS 93, 1993

Selectivity.

Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang

Proceedings of the Computing and Information, 1993

P-Selective Sets, and Reducing Search to Decision vs. Self-Reducability.

Ashish V. Naik, Mitsunori Ogiwara, Alan L. Selman

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

A Survey of One-Way Functions in Complexity Theory.

Alan L. Selman

Math. Syst. Theory, 1992

1991

Complexity Classes for Partial Functions.

Alan L. Selman

Bull. EATCS, 1991

1990

Hard Promise Problems and Nonuniform Complexity.

Luc Longpré, Alan L. Selman

Proceedings of the STACS 90, 1990

One-Way Functions in Complexity Theory.

Alan L. Selman

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989

Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography.

Steven Homer, Alan L. Selman

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Promise Problems Complete for Complexity Classes

Alan L. Selman

Inf. Comput., August, 1988

Natural Self-Reducible Sets.

Alan L. Selman

SIAM J. Comput., 1988

Complexity Measures for Public-Key Cryptosystems.

Joachim Grollmann, Alan L. Selman

SIAM J. Comput., 1988

1987

A Hierarchy Theorem for Almost Everywhere Complex Sets With Application to Polynomial Complexity Degrees.

John G. Geske, Dung T. Huynh, Alan L. Selman

Proceedings of the STACS 87, 1987

1986

Relativizing complexity classes with sparse oracles.

Timothy J. Long, Alan L. Selman

J. ACM, 1986

1985

Hard-Core Theorems for Complexity Classes

Shimon Even, Alan L. Selman, Yacov Yacobi

J. ACM, January, 1985

Qualitative Relativizations of Complexity Classes.

Ronald V. Book, Timothy J. Long, Alan L. Selman

J. Comput. Syst. Sci., 1985

1984

The Complexity of Promise Problems with Applications to Public-Key Cryptography

Shimon Even, Alan L. Selman, Yacov Yacobi

Inf. Control., May, 1984

Quantitative Relativizations of Complexity Classes.

Ronald V. Book, Timothy J. Long, Alan L. Selman

SIAM J. Comput., 1984

Characterizations of Reduction Classes Modulo Oracle Conditions.

Ronald V. Book, Alan L. Selman

Math. Syst. Theory, 1984

Complexity Measures for Public-Key Cryptosystems (Preliminary Report)

Joachim Grollmann, Alan L. Selman

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Sparse Oracles and Uniform Complexity Classes

José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Positive Relativizations of Complexity Classes.

Alan L. Selman, Xu Mei-Rui, Ronald V. Book

SIAM J. Comput., 1983

Controlled relativizations of P and NP.

Ronald V. Book, Timothy J. Long, Alan L. Selman

Proceedings of the Theoretical Computer Science, 1983

1982

Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity

Alan L. Selman

Inf. Control., January, 1982

Reductions on NP and P-Selective Sets.

Alan L. Selman

Theor. Comput. Sci., 1982

The Complexity of Promise Problems.

Alan L. Selman, Yacov Yacobi

Proceedings of the Automata, 1982

1981

Some Observations on NP, Real Numbers and P-Selective Sets.

Alan L. Selman

J. Comput. Syst. Sci., 1981

1979

P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP.

Alan L. Selman

Proceedings of the Automata, 1979

1978

Polynomial Time Enumeration Reducibility.

Alan L. Selman

SIAM J. Comput., 1978

1977

Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.

Ronald V. Book, Celia Wrathall, Alan L. Selman, David P. Dobkin

Math. Syst. Theory, 1977

1976

A Second Step toward the Polynomial Hierarchy

Theodore P. Baker, Alan L. Selman

Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975

A Comparison of Polynomial Time Reducibilities.

Richard E. Ladner, Nancy A. Lynch, Alan L. Selman

Theor. Comput. Sci., 1975

1974

Turing Machines and the Spectra of First-Order Formulas.

Neil D. Jones, Alan L. Selman

J. Symb. Log., 1974

Comparisons of Polynomial-Time Reducibilities

Richard E. Ladner, Nancy A. Lynch, Alan L. Selman

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

Neil D. Jones, Alan L. Selman

Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972