Alan L. Selman

120 papers A* 7A 16B 4C 2Misc 2Journal 75Unranked 8

Year	Rank	Type	Title / Venue / Authors
2017	J	`jnl`	50 Years of TOCS. Theory Comput. Syst. Alan L. Selman, Arnold L. Rosenberg
2017	—	`conf`	Introduction to Autoreducibility and Mitoticity. Computability and Complexity Christian Glaßer, Dung T. Nguyen, Alan L. Selman, Maximilian Witek
2016	J	`jnl`	A thirty Year old conjecture about promise problems. Comput. Complex. Andrew Hughes, Debasis Mandal, Aduri Pavan, Nathan Russell, Alan L. Selman
2016	J	`jnl`	Structural Properties of Nonautoreducible Sets. ACM Trans. Comput. Theory Dung T. Nguyen, Alan L. Selman
2014	J	`jnl`	Disjoint NP-Pairs and Propositional Proof Systems. SIGACT News Christian Glaßer, Andrew Hughes, Alan L. Selman, Nils Wisiol
2014	A	`conf`	Non-autoreducible Sets for NEXP. STACS Dung T. Nguyen, Alan L. Selman
2014	—	`ch.`	Turing and the development of computational complexity. Turing's Legacy Steven Homer, Alan L. Selman
2013	—	`conf`	Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. ICALP (1) Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek
2013	J	`jnl`	Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. Electron. Colloquium Comput. Complex. Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek
2013	J	`jnl`	Non-autoreducible Sets for NEXP. Electron. Colloquium Comput. Complex. Dung T. Nguyen, Alan L. Selman
2012	—	`conf`	A Thirty Year Old Conjecture about Promise Problems. ICALP (1) Andrew Hughes, Aduri Pavan, Nathan Russell, Alan L. Selman
2011	—	`book`	Computability and Complexity Theory, Second Edition. Steven Homer, Alan L. Selman
2011	J	`jnl`	Foreword. J. Comput. Syst. Sci. Jin-Yi Cai, Alan L. Selman
2009	J	`jnl`	Non-mitotic sets. Theor. Comput. Sci. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang
2009	J	`jnl`	The Informational Content of Canonical Disjoint NP-Pairs. Int. J. Found. Comput. Sci. Christian Glaßer, Alan L. Selman, Liyu Zhang
2008	J	`jnl`	Splitting NP-Complete Sets. SIAM J. Comput. Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2008	J	`jnl`	The complexity of unions of disjoint sets. J. Comput. Syst. Sci. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner
2007	J	`jnl`	Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci. Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
2007	J	`jnl`	Canonical disjoint NP-pairs of propositional proof systems. Theor. Comput. Sci. Christian Glaßer, Alan L. Selman, Liyu Zhang
2007	—	`conf`	Non-mitotic Sets. FSTTCS Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang
2007	J	`jnl`	Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. Theor. Comput. Sci. Aduri Pavan, Alan L. Selman, Samik Sengupta, N. V. Vinodchandran
2007	A	`conf`	The Complexity of Unions of Disjoint Sets. STACS Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner
2007	Misc	`conf`	The Informational Content of Canonical Disjoint NP-Pairs. COCOON Christian Glaßer, Alan L. Selman, Liyu Zhang
2007	J	`jnl`	The Informational Content of Canonical Disjoint NP-Pairs. Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Liyu Zhang
2006	C	`conf`	Mitosis in Computational Complexity. TAMC Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2006	J	`jnl`	Non-Mitotic Sets. Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang
2006	J	`jnl`	Properties of NP-Complete Sets. SIAM J. Comput. Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
2006	A	`conf`	Redundancy in Complete Sets. STACS Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2006	—	`conf`	Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems. Essays in Memory of Shimon Even Christian Glaßer, Alan L. Selman, Liyu Zhang
2006	J	`jnl`	The Complexity of Unions of Disjoint Sets. Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner
2006	—	`ed.`	Theoretical Computer Science, Essays in Memory of Shimon Even Essays in Memory of Shimon Even Oded Goldreich, Arnold L. Rosenberg, Alan L. Selman
2005	J	`jnl`	Autoreducibility, Mitoticity, and Immunity Electron. Colloquium Comput. Complex. Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
2005	B	`conf`	Autoreducibility, Mitoticity, and Immunity. MFCS Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
2005	B	`conf`	Canonical Disjoint NP-Pairs of Propositional Proof Systems. MFCS Christian Glaßer, Alan L. Selman, Liyu Zhang
2005	J	`jnl`	Reductions between disjoint NP-Pairs. Inf. Comput. Christian Glaßer, Alan L. Selman, Samik Sengupta
2005	J	`jnl`	Redundancy in Complete Sets Electron. Colloquium Comput. Complex. Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2005	J	`jnl`	Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Liyu Zhang
2004	J	`jnl`	Bi-immunity separates strong NP-completeness notions. Inf. Comput. Aduri Pavan, Alan L. Selman
2004	J	`jnl`	Canonical Disjoint NP-Pairs of Propositional Proof Systems Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Liyu Zhang
2004	J	`jnl`	Disjoint NP-Pairs. SIAM J. Comput. Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang
2004	A	`conf`	Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. CCC Alan L. Selman, Samik Sengupta
2004	J	`jnl`	Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy Electron. Colloquium Comput. Complex. Alan L. Selman, Samik Sengupta
2004	J	`jnl`	Properties of NP-Complete Sets Electron. Colloquium Comput. Complex. Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
2004	A	`conf`	Properties of NP-Complete Sets. CCC Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
2004	A	`conf`	Reductions between Disjoint NP-Pairs. CCC Christian Glaßer, Alan L. Selman, Samik Sengupta
2003	J	`jnl`	Disjoint NP-Pairs Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang
2003	A	`conf`	Disjoint NP-Pairs. CCC Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang
2003	J	`jnl`	Reductions between Disjoint NP-Pairs Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Samik Sengupta
2002	J	`jnl`	Bi-Immunity Separates Strong NP-Completeness Notions Electron. Colloquium Comput. Complex. Aduri Pavan, Alan L. Selman
2002	A	`conf`	Bi-Immunity Separates Strong NP-Completeness Notions. STACS Aduri Pavan, Alan L. Selman
2001	—	`book`	Computability and Complexity Theory. Steven Homer, Alan L. Selman
2001	J	`jnl`	Distributionally Hard Languages. Theory Comput. Syst. Lance Fortnow, Aduri Pavan, Alan L. Selman
2001	J	`jnl`	Editorial Statement. Theory Comput. Syst. Alan L. Selman
2001	A	`conf`	Separation of NP-Completeness Notions. CCC Aduri Pavan, Alan L. Selman
2001	J	`jnl`	Separation of NP-Completeness Notions. SIAM J. Comput. Aduri Pavan, Alan L. Selman
2001	J	`jnl`	Separation of NP-completeness Notions Electron. Colloquium Comput. Complex. Aduri Pavan, Alan L. Selman
2001	J	`jnl`	The history and contribution of theoretical computer science. Adv. Comput. John E. Savage, Alan L. Selman, Carl Smith
2000	J	`jnl`	Complete distributional problems, hard languages, and resource-bounded measure. Theor. Comput. Sci. Aduri Pavan, Alan L. Selman
1999	J	`jnl`	Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets. Comput. Complex. Ashish V. Naik, Alan L. Selman
1999	J	`jnl`	Complements of Multivalued Functions. Chic. J. Theor. Comput. Sci. Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
1999	Misc	`conf`	Distributionally-Hard Languages. COCOON Lance Fortnow, Aduri Pavan, Alan L. Selman
1999	J	`jnl`	Fine Separation of Average-Time Complexity Classes. SIAM J. Comput. Jin-Yi Cai, Alan L. Selman
1998	J	`jnl`	A Hierarchy Based on Output Multiplicity. Theor. Comput. Sci. Ashish V. Naik, John D. Rogers, James S. Royer, Alan L. Selman
1998	J	`jnl`	Writing and Editing Complexity Theory: Tales and Tools CoRR Lane A. Hemaspaandra, Alan L. Selman
1998	J	`jnl`	Writing and editing complexity theory: tales and tools. SIGACT News Lane A. Hemaspaandra, Alan L. Selman
1997	J	`jnl`	Oracles that Compute Values. SIAM J. Comput. Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman
1997	J	`jnl`	Strategic directions in research in theory of computing. SIGACT News 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
1996	A	`conf`	A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP. CCC Ashish V. Naik, Alan L. Selman
1996	A	`conf`	Complements of Multivalued Functions. CCC Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
1996	J	`jnl`	Computing Solutions Uniquely Collapses the Polynomial Hierarchy Electron. Colloquium Comput. Complex. Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman
1996	J	`jnl`	Computing Solutions Uniquely Collapses the Polynomial Hierarchy. SIAM J. Comput. Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman
1996	A	`conf`	Fine Separation of Average Time Complexity Classes. STACS Jin-Yi Cai, Alan L. Selman
1996	A	`conf`	Much Ado about Functions. CCC Alan L. Selman
1996	J	`jnl`	P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility. J. Comput. Syst. Sci. Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman
1995	J	`jnl`	Average Time Complexity Classes Electron. Colloquium Comput. Complex. Jin-Yi Cai, Alan L. Selman
1995	J	`jnl`	Nondeterministically Selective Sets. Int. J. Found. Comput. Sci. Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang
1995	J	`jnl`	Wide Area Technical Report Service: Technical Reports Online. Commun. ACM James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman
1994	J	`jnl`	A Taxonomy of Complexity Classes of Functions. J. Comput. Syst. Sci. Alan L. Selman
1994	B	`conf`	Computing Solutions Uniquely collapses the Polynomial Hierarchy. ISAAC Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman
1994	J	`jnl`	Wide area technical report service - technical reports online. SIGACT News James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman
1993	—	`ch.`	Complexity Classes for Partial Functions. Current Trends in Theoretical Computer Science Alan L. Selman
1993	J	`jnl`	Hard Promise Problems and Nonuniform Complexity. Theor. Comput. Sci. Luc Longpré, Alan L. Selman
1993	A	`conf`	On Using Oracles That Compute Values. STACS Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman
1993	—	`conf`	P-Selective Sets, and Reducing Search to Decision vs. Self-Reducability. SCT Ashish V. Naik, Mitsunori Ogiwara, Alan L. Selman
1993	C	`conf`	Selectivity. ICCI Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang
1992	J	`jnl`	A Survey of One-Way Functions in Complexity Theory. Math. Syst. Theory Alan L. Selman
1992	J	`jnl`	Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. J. Comput. Syst. Sci. Steven Homer, Alan L. Selman
1991	J	`jnl`	Complexity Classes for Partial Functions. Bull. EATCS Alan L. Selman
1990	A	`conf`	Hard Promise Problems and Nonuniform Complexity. STACS Luc Longpré, Alan L. Selman
1990	B	`conf`	One-Way Functions in Complexity Theory. MFCS Alan L. Selman
1989	—	`conf`	Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. SCT Steven Homer, Alan L. Selman
1988	J	`jnl`	Complexity Measures for Public-Key Cryptosystems. SIAM J. Comput. Joachim Grollmann, Alan L. Selman
1988	J	`jnl`	Natural Self-Reducible Sets. SIAM J. Comput. Alan L. Selman
1988	J	`jnl`	Promise Problems Complete for Complexity Classes Inf. Comput. Alan L. Selman
1987	A	`conf`	A Hierarchy Theorem for Almost Everywhere Complex Sets With Application to Polynomial Complexity Degrees. STACS John G. Geske, Dung T. Huynh, Alan L. Selman
1986	J	`jnl`	Relativizing complexity classes with sparse oracles. J. ACM Timothy J. Long, Alan L. Selman
1986	—	`ed.`	Structure in Complexity Theory, Proceedings of the Conference hold at the University of California, Berkeley, California, USA, June 2-5, 1986 SCT Alan L. Selman
1985	J	`jnl`	Hard-Core Theorems for Complexity Classes J. ACM Shimon Even, Alan L. Selman, Yacov Yacobi
1985	J	`jnl`	Qualitative Relativizations of Complexity Classes. J. Comput. Syst. Sci. Ronald V. Book, Timothy J. Long, Alan L. Selman
1984	J	`jnl`	Characterizations of Reduction Classes Modulo Oracle Conditions. Math. Syst. Theory Ronald V. Book, Alan L. Selman
1984	A*	`conf`	Complexity Measures for Public-Key Cryptosystems (Preliminary Report) FOCS Joachim Grollmann, Alan L. Selman
1984	J	`jnl`	Quantitative Relativizations of Complexity Classes. SIAM J. Comput. Ronald V. Book, Timothy J. Long, Alan L. Selman
1984	A*	`conf`	Sparse Oracles and Uniform Complexity Classes FOCS José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman
1984	J	`jnl`	The Complexity of Promise Problems with Applications to Public-Key Cryptography Inf. Control. Shimon Even, Alan L. Selman, Yacov Yacobi
1983	—	`conf`	Controlled relativizations of P and NP. Theoretical Computer Science Ronald V. Book, Timothy J. Long, Alan L. Selman
1983	J	`jnl`	Positive Relativizations of Complexity Classes. SIAM J. Comput. Alan L. Selman, Xu Mei-Rui, Ronald V. Book
1982	J	`jnl`	Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity Inf. Control. Alan L. Selman
1982	J	`jnl`	Reductions on NP and P-Selective Sets. Theor. Comput. Sci. Alan L. Selman
1982	A*	`conf`	The Complexity of Promise Problems. ICALP Alan L. Selman, Yacov Yacobi
1981	J	`jnl`	Some Observations on NP, Real Numbers and P-Selective Sets. J. Comput. Syst. Sci. Alan L. Selman
1979	J	`jnl`	A Second Step Toward the Polynomial Hierarchy. Theor. Comput. Sci. Theodore P. Baker, Alan L. Selman
1979	A*	`conf`	P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. ICALP Alan L. Selman
1979	J	`jnl`	P-selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. Math. Syst. Theory Alan L. Selman
1978	J	`jnl`	Polynomial Time Enumeration Reducibility. SIAM J. Comput. Alan L. Selman
1977	J	`jnl`	Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture. Math. Syst. Theory Ronald V. Book, Celia Wrathall, Alan L. Selman, David P. Dobkin
1976	A*	`conf`	A Second Step toward the Polynomial Hierarchy FOCS Theodore P. Baker, Alan L. Selman
1975	J	`jnl`	A Comparison of Polynomial Time Reducibilities. Theor. Comput. Sci. Richard E. Ladner, Nancy A. Lynch, Alan L. Selman
1974	A*	`conf`	Comparisons of Polynomial-Time Reducibilities STOC Richard E. Ladner, Nancy A. Lynch, Alan L. Selman
1974	J	`jnl`	Turing Machines and the Spectra of First-Order Formulas. J. Symb. Log. Neil D. Jones, Alan L. Selman
1972	A*	`conf`	Turing Machines and the Spectra of First-Order Formulas with Equality STOC Neil D. Jones, Alan L. Selman