UB - University at Buffalo, The State University of New York Computer Science and Engineering

Roles

  • Professor

Books

Research Areas

Theory and Algorithms
image of theory

Methods and techniques for developing efficient algorithms, especially graph algorithms, parallel algorithms and architectures, graph drawing, computational geometry, and group testing algorithms. Obstacles to proving non-trivial lower bounds in complexity theory. Properties of complexity classes, with relationships between classes and with identification of properties of problems that affect their computational complexity. | More »

Courses

Technical Reports

2011-06
Homer, Steven; Selman, Alan L.. Turing and the Development of Computational Complexity, September 8, 2011.
2006-14
Glasser, Christian; Selman, Alan L.; Travers, Stephen; Wagner, Klaus. The Complexity of Unions of Disjoint Sets., June 26, 2006.
2006-13
Glasser, Christian; Selman, Alan L.; Travers, Stephen; Zhang, Liyu. Non-Mitotic Sets., June 22, 2006.
2005-19
Glasser, Christian; Selman, Alan L.; Zhang, Liyu. Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems, July 7, 2005.
2005-18
Glasser, Christian; Pavan, A.; Selman, Alan L.; Zhang, Liyu. Redundancy in Complete Sets, July 7, 2005.
2004-22
Glasser, Christian; Ogihara, Mitsunori; Pavan, A.; Selman, Alan L.; Zhang, Liyu. Autoreducibility, Mitoticity, and Immunity, December 21, 2004.
2004-17
Glasser, Christian; Selman, Alan L.; Zhang, Liyu. Canonical Disjoint NP-Pairs of Propositional Proof Systems, November 19, 2004.
2004-03
Glasser, Christian; Pavan, A.; Selman, Alan L.; Sengupta, Samik. Properties of NP-Complete Sets, January 15, 2004.
2003-04
Glasser, Christian; Selman, Alan L.; Sengupta, S.. Reductions between Disjoint NP-Pairs, April 21, 2003.
2003-02
Glasser, Christian; Selman, Alan L.; Sengupta, Samik; Zhang, Liyu. Disjoint NP-Pairs, February 17, 2003.
2004-01
Selman, Alan L.; Sengupta, S.. Polylogarithmic-round Interactive Proofs for coNP, September 2, 2003.
2001-02
Pavan, A.; Selman, Alan L.. Separation of NP-completeness Notions, January 16, 2001.
99-02
Fortnow, L.; Pavan, A.; Selman, Alan L.. Distributionally-Hard Languages, April 26, 1999.
97-13
Naik, Ashish V.; Rogers, John, D.; Royer, James S.; Selman, Alan L.. A Hierarchy Based on Output Multiplicity, August 5, 1997.
97-01
Pavan, A.; Selman, Alan L.. Complete Distributional Problems, Hard Languages, and Resource-Bounded Measure, February 6, 1997.
95-51
Fenner, Stephen; Green, Frederic; Homer, Stephen; Selman, Alan L.; Thierauf, Thomas; Vollmer, Heribe. Complements of Multivalued Functions, November 6, 1995.
95-16
Cai, Jin-Yi; Selman, Alan L.. Average Time Complexity Classes, March 31, 1995.
94-02
Cai, Jin-Yi; Naik, Ashish V.; Selman, Alan L.. On P-selective sets and Adaptive versus Nonadaptive Queries to NP, February 2, 1994.
93-29
Hemaspaandra, Lane A.; Hoene, Albrecht; Naik, Ashish V.; Ogiwara, Mitsunori; Selman, Alan L.; Thiera. Selectivity: Reductions, Nondeterminism, and Function Classes, August 18, 1993.
93-28
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogiwara, Mitsunori; Selman, Alan L.. Computing Solutions Uniquely Collapses the Polynomial Hierarchy, August 17, 1993.
93-21
Hemaspaandra, Edith; Naik, Ashish V.; Ogiwara, Mitsunori; Selman, Alan L.. P-Selective Sets, and Reducing Search to Decision vs. Self-Reducibility, July 30, 1993.
93-05
Fenner, Stephen; Homer, Stephen; Ogiwara, Mitsunori; Selman, Alan L.. On Using Oracles That Compute Values, February 17, 1993.
91-12
Selman, Alan L.. A Taxonomy of Complexity Class of Functions, June 1, 1992.
91-04
Homer, Stephen; Selman, Alan L.. Complexity Theory, June 8, 1992.
Valid XHTML 1.0 Transitional