Alan L. Selman

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek: Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. Electronic Colloquium on Computational Complexity (ECCC) 20: 47 (2013)

Dung Nguyen, Alan L. Selman: Non-autoreducible Sets for NEXP. Electronic Colloquium on Computational Complexity (ECCC) 20: 63 (2013)

Andrew Hughes, Aduri Pavan, Nathan Russell, Alan L. Selman: A Thirty Year Old Conjecture about Promise Problems. ICALP (1) 2012: 473-484

Steven Homer, Alan L. Selman: Computability and Complexity Theory, Second Edition. Texts in computer science, Springer 2011, isbn 978-1-4614-0681-5, pp. I-XVI, 1-298

Jin-yi Cai, Alan L. Selman: Foreword. J. Comput. Syst. Sci. 77(1): 1-2 (2011)

Christian Glaßer, Alan L. Selman, Liyu Zhang: The Informational Content of Canonical Disjoint NP-Pairs. Int. J. Found. Comput. Sci. 20(3): 501-522 (2009)

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang: Non-mitotic sets. Theor. Comput. Sci. 410(21-23): 2011-2023 (2009)

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner: The complexity of unions of disjoint sets. J. Comput. Syst. Sci. 74(7): 1173-1187 (2008)

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang: Splitting NP-Complete Sets. SIAM J. Comput. 37(5): 1517-1535 (2008)

Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang: Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci. 73(5): 735-754 (2007)

Christian Glaßer, Alan L. Selman, Liyu Zhang: Canonical disjoint NP-pairs of propositional proof systems. Theor. Comput. Sci. 370(1-3): 60-73 (2007)

Aduri Pavan, Alan L. Selman, Samik Sengupta, N. V. Vinodchandran: Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. Theor. Comput. Sci. 385(1-3): 167-178 (2007)

Christian Glaßer, Alan L. Selman, Liyu Zhang: The Informational Content of Canonical Disjoint NP-Pairs. COCOON 2007: 307-317

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang: Non-mitotic Sets. FSTTCS 2007: 146-157

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner: The Complexity of Unions of Disjoint Sets. STACS 2007: 248-259

Christian Glaßer, Alan L. Selman, Liyu Zhang: The Informational Content of Canonical Disjoint NP-Pairs. Electronic Colloquium on Computational Complexity (ECCC) 14(018) (2007)

Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta: Properties of NP-Complete Sets. SIAM J. Comput. 36(2): 516-542 (2006)

Christian Glaßer, Alan L. Selman, Liyu Zhang: Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems. Essays in Memory of Shimon Even 2006: 241-253

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang: Redundancy in Complete Sets. STACS 2006: 444-454

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang: Mitosis in Computational Complexity. TAMC 2006: 61-67

Oded Goldreich, Arnold L. Rosenberg, Alan L. Selman (Eds.): Theoretical Computer Science, Essays in Memory of Shimon Even. Lecture Notes in Computer Science 3895, Springer 2006, isbn 3-540-32880-7

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner: The Complexity of Unions of Disjoint Sets. Electronic Colloquium on Computational Complexity (ECCC) 13(069) (2006)

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang: Non-Mitotic Sets. Electronic Colloquium on Computational Complexity (ECCC) 13(090) (2006)

Christian Glaßer, Alan L. Selman, Samik Sengupta: Reductions between disjoint NP-Pairs. Inf. Comput. 200(2): 247-267 (2005)

Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang: Autoreducibility, Mitoticity, and Immunity. MFCS 2005: 387-398

Christian Glaßer, Alan L. Selman, Liyu Zhang: Canonical Disjoint NP-Pairs of Propositional Proof Systems. MFCS 2005: 399-409

Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang: Autoreducibility, Mitoticity, and Immunity. Electronic Colloquium on Computational Complexity (ECCC)(011) (2005)

Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang: Redundancy in Complete Sets. Electronic Colloquium on Computational Complexity (ECCC)(068) (2005)

Christian Glaßer, Alan L. Selman, Liyu Zhang: Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems. Electronic Colloquium on Computational Complexity (ECCC)(072) (2005)

Aduri Pavan, Alan L. Selman: Bi-immunity separates strong NP-completeness notions. Inf. Comput. 188(1): 116-126 (2004)

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang: Disjoint NP-Pairs. SIAM J. Comput. 33(6): 1369-1416 (2004)

Christian Glaßer, Alan L. Selman, Samik Sengupta: Reductions between Disjoint NP-Pairs. IEEE Conference on Computational Complexity 2004: 42-53

Alan L. Selman, Samik Sengupta: Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. IEEE Conference on Computational Complexity 2004: 82-90

Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta: Properties of NP-Complete Sets. IEEE Conference on Computational Complexity 2004: 184-197

Alan L. Selman, Samik Sengupta: Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy. Electronic Colloquium on Computational Complexity (ECCC)(007) (2004)

Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta: Properties of NP-Complete Sets. Electronic Colloquium on Computational Complexity (ECCC)(019) (2004)

Christian Glaßer, Alan L. Selman, Liyu Zhang: Canonical Disjoint NP-Pairs of Propositional Proof Systems. Electronic Colloquium on Computational Complexity (ECCC)(106) (2004)

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang: Disjoint NP-Pairs. IEEE Conference on Computational Complexity 2003: 313-332

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang: Disjoint NP-Pairs. Electronic Colloquium on Computational Complexity (ECCC) 10(011) (2003)

Christian Glaßer, Alan L. Selman, Samik Sengupta: Reductions between Disjoint NP-Pairs. Electronic Colloquium on Computational Complexity (ECCC) 10(027) (2003)

Aduri Pavan, Alan L. Selman: Bi-Immunity Separates Strong NP-Completeness Notions. STACS 2002: 408-418

Aduri Pavan, Alan L. Selman: Bi-Immunity Separates Strong NP-Completeness Notions. Electronic Colloquium on Computational Complexity (ECCC)(005) (2002)

John E. Savage, Alan L. Selman, Carl Smith: The history and contribution of theoretical computer science. Advances in Computers 55: 171-183 (2001)

Alan L. Selman: Editorial Statement. Theory Comput. Syst. 34(1): 1 (2001)

Lance Fortnow, Aduri Pavan, Alan L. Selman: Distributionally Hard Languages. Theory Comput. Syst. 34(3): 245-261 (2001)

Aduri Pavan, Alan L. Selman: Separation of NP-Completeness Notions. SIAM J. Comput. 31(3): 906-918 (2001)

Aduri Pavan, Alan L. Selman: Separation of NP-Completeness Notions. IEEE Conference on Computational Complexity 2001: 78-89

Aduri Pavan, Alan L. Selman: Separation of NP-completeness Notions. Electronic Colloquium on Computational Complexity (ECCC) 8(32) (2001)

Aduri Pavan, Alan L. Selman: Complete distributional problems, hard languages, and resource-bounded measure. Theor. Comput. Sci. 234(1-2): 273-286 (2000)

Ashish V. Naik, Alan L. Selman: Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets. Computational Complexity 8(2): 169-187 (1999)

Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer: Complements of Multivalued Functions. Chicago J. Theor. Comput. Sci. 1999 (1999)

Jin-yi Cai, Alan L. Selman: Fine Separation of Average-Time Complexity Classes. SIAM J. Comput. 28(4): 1310-1325 (1999)

Lance Fortnow, Aduri Pavan, Alan L. Selman: Distributionally-Hard Languages. COCOON 1999: 184-193

Lane A. Hemaspaandra, Alan L. Selman: Writing and editing complexity theory: tales and tools. SIGACT News 29(4): 20-27 (1998)

Ashish V. Naik, John D. Rogers, James S. Royer, Alan L. Selman: A Hierarchy Based on Output Multiplicity. Theor. Comput. Sci. 207(1): 131-157 (1998)

Lane A. Hemaspaandra, Alan L. Selman: Writing and Editing Complexity Theory: Tales and Tools. CoRR cs.GL/9811005 (1998)

Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman: Oracles that Compute Values. SIAM J. Comput. 26(4): 1043-1065 (1997)

Anne Condon, Faith 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: Strategic directions in research in theory of computing. SIGACT News 28(3): 75-93 (1997)

Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility. J. Comput. Syst. Sci. 53(2): 194-209 (1996)

Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely Collapses the Polynomial Hierarchy. SIAM J. Comput. 25(4): 697-708 (1996)

Alan L. Selman: Much Ado about Functions. IEEE Conference on Computational Complexity 1996: 198-212

Ashish V. Naik, Alan L. Selman: A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP. IEEE Conference on Computational Complexity 1996: 224-232

Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer: Complements of Multivalued Functions. IEEE Conference on Computational Complexity 1996: 260-269

Jin-yi Cai, Alan L. Selman: Fine Separation of Average Time Complexity Classes. STACS 1996: 331-343

Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely Collapses the Polynomial Hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 3(27) (1996)

James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman: Wide Area Technical Report Service: Technical Reports Online. Commun. ACM 38(4): 45 (1995)

Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang: Nondeterministically Selective Sets. Int. J. Found. Comput. Sci. 6(4): 403-416 (1995)

Jin-yi Cai, Alan L. Selman: Average Time Complexity Classes. Electronic Colloquium on Computational Complexity (ECCC) 2(19) (1995)

Alan L. Selman: A Taxonomy of Complexity Classes of Functions. J. Comput. Syst. Sci. 48(2): 357-381 (1994)

James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman: Wide area technical report service - technical reports online. SIGACT News 25(3): 124-127 (1994)

Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely collapses the Polynomial Hierarchy. ISAAC 1994: 56-64

Luc Longpré, Alan L. Selman: Hard Promise Problems and Nonuniform Complexity. Theor. Comput. Sci. 115(2): 277-290 (1993)

Ashish V. Naik, Mitsunori Ogiwara, Alan L. Selman: P-Selective Sets, and Reducing Search to Decision vs. Self-Reducability. Structure in Complexity Theory Conference 1993: 52-64

Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang: Selectivity. ICCI 1993: 55-59

Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman: On Using Oracles That Compute Values. STACS 1993: 398-407

Steven Homer, Alan L. Selman: Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. J. Comput. Syst. Sci. 44(2): 287-301 (1992)

Alan L. Selman: A Survey of One-Way Functions in Complexity Theory. Mathematical Systems Theory 25(3): 203-221 (1992)

Alan L. Selman: Complexity Classes for Partial Functions. Bulletin of the EATCS 45: 114-130 (1991)

Alan L. Selman: One-Way Functions in Complexity Theory. MFCS 1990: 88-104

Luc Longpré, Alan L. Selman: Hard Promise Problems and Nonuniform Complexity. STACS 1990: 216-226

Steven Homer, Alan L. Selman: Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. Structure in Complexity Theory Conference 1989: 3-14

Alan L. Selman: Promise Problems Complete for Complexity Classes. Inf. Comput. 78(2): 87-97 (1988)

Joachim Grollmann, Alan L. Selman: Complexity Measures for Public-Key Cryptosystems. SIAM J. Comput. 17(2): 309-335 (1988)

Alan L. Selman: Natural Self-Reducible Sets. SIAM J. Comput. 17(5): 989-996 (1988)

John G. Geske, Dung T. Huynh, Alan L. Selman: A Hierarchy Theorem for Almost Everywhere Complex Sets With Application to Polynomial Complexity Degrees. STACS 1987: 125-135

Timothy J. Long, Alan L. Selman: Relativizing complexity classes with sparse oracles. J. ACM 33(3): 618-627 (1986)

Alan L. Selman (Ed.): Structure in Complexity Theory, Proceedings of the Conference hold at the University of California, Berkeley, California, June 2-5, 1986. Lecture Notes in Computer Science 223, Springer 1986, isbn 3-540-16486-3

Shimon Even, Alan L. Selman, Yacov Yacobi: Hard-Core Theorems for Complexity Classes. J. ACM 32(1): 205-217 (1985)

Ronald V. Book, Timothy J. Long, Alan L. Selman: Qualitative Relativizations of Complexity Classes. J. Comput. Syst. Sci. 30(3): 395-413 (1985)

Shimon Even, Alan L. Selman, Yacov Yacobi: The Complexity of Promise Problems with Applications to Public-Key Cryptography. Information and Control 61(2): 159-173 (1984)

Ronald V. Book, Alan L. Selman: Characterizations of Reduction Classes Modulo Oracle Conditions. Mathematical Systems Theory 17(4): 263-277 (1984)

Ronald V. Book, Timothy J. Long, Alan L. Selman: Quantitative Relativizations of Complexity Classes. SIAM J. Comput. 13(3): 461-487 (1984)

José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman: Sparse Oracles and Uniform Complexity Classes. FOCS 1984: 308-311

Joachim Grollmann, Alan L. Selman: Complexity Measures for Public-Key Cryptosystems (Preliminary Report). FOCS 1984: 495-503

Alan L. Selman, Xu Mei-Rui, Ronald V. Book: Positive Relativizations of Complexity Classes. SIAM J. Comput. 12(3): 565-579 (1983)

Ronald V. Book, Timothy J. Long, Alan L. Selman: Controlled relativizations of P and NP. Theoretical Computer Science 1983: 85-90

Alan L. Selman: Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity. Information and Control 52(1): 36-51 (1982)

Alan L. Selman: Reductions on NP and P-Selective Sets. Theor. Comput. Sci. 19: 287-304 (1982)

Alan L. Selman, Yacov Yacobi: The Complexity of Promise Problems. ICALP 1982: 502-509

Alan L. Selman: Some Observations on NP, Real Numbers and P-Selective Sets. J. Comput. Syst. Sci. 23(3): 326-332 (1981)

Alan L. Selman: P-selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. Mathematical Systems Theory 13: 55-65 (1979)

Theodore P. Baker, Alan L. Selman: A Second Step Toward the Polynomial Hierarchy. Theor. Comput. Sci. 8: 177-187 (1979)

Alan L. Selman: P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. ICALP 1979: 546-555

Alan L. Selman: Polynomial Time Enumeration Reducibility. SIAM J. Comput. 7(4): 440-457 (1978)

Ronald V. Book, Celia Wrathall, Alan L. Selman, David P. Dobkin: Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture. Mathematical Systems Theory 11: 1-8 (1977)

Theodore P. Baker, Alan L. Selman: A Second Step toward the Polynomial Hierarchy. FOCS 1976: 71-75

Richard E. Ladner, Nancy A. Lynch, Alan L. Selman: A Comparison of Polynomial Time Reducibilities. Theor. Comput. Sci. 1(2): 103-123 (1975)

Neil D. Jones, Alan L. Selman: Turing Machines and the Spectra of First-Order Formulas. J. Symb. Log. 39(1): 139-150 (1974)

Richard E. Ladner, Nancy A. Lynch, Alan L. Selman: Comparisons of Polynomial-Time Reducibilities. STOC 1974: 110-121

Neil D. Jones, Alan L. Selman: Turing Machines and the Spectra of First-Order Formulas with Equality. STOC 1972: 157-167