UB Logo CSE Logo
Alan Selman, Professor
Alan Selman
Department of Computer Science and Engineering
University at Buffalo, The State University of New York
201 Bell Hall
Buffalo, NY 14260-2000
U.S.A.
Phone: (716) 645-4742
FAX: (716) 645-3464
Email: selman@@buffalo.edu
Picture

Computability and Complexity Theory, by Steven Homer and Alan L. Selman, Springer Verlag NY, 2001

Report of an NSF-Sponsored Workshop on Research in Theoretical Computer Science, 1999

Teaching Activities

Recent Activities

Professor Selman is a Fellow of the ACM, recipient of a Humboldt research award (2005), an Invitation Fellowship for research in Japan from the Japan Society for the Promotion of Science (1996), and a Fulbright scholar (1981).
Curriculum Vitae: (pdf)

Recent Papers

  1. C. Glasser, A. Selman, and L. Zhang. The Informational Content of Canonical Disjoint NP-Pairs. (pdf) 13th Annual International Computing and Combinatorics Conference, Banff, Canada, July 2007.
  2. C. Glasser, A. Pavan, A. Selman, and L. Zhang. Mitosis in Computational Complexity. (pdf) Text of my plenary lecture at the Third International Conference, Theory and Applications of Models of Computation, Beijing, May, 2006.
  3. C. Glasser, A. Selman, S. Travers, and K. Wagner. The Complexity of Unions of Disjoint Sets. (pdf)

  4. C. Glasser, A. Selman, S. Travers, and L. Zhang. Non-Mitotic Sets. (pdf)

  5. C. Glasser, A. Selman, L. Zhang. Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems. (ps) (pdf) In Theoretical Computer Science, Essays in Memory of Shimon Even, eds. O. Goldreich, A. Rosenberg, and A. Selman, LNCS 3895, Springer, 2006.

  6. C. Glasser, A. Pavan, A. Selman, and L. Zhang. Redundancy in Complete Sets. (ps) (pdf) 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 2006.

  7. C. Glasser, M. Ogihara, A. Pavan, A. Selman, and L. Zhang. Autoreducibility, Mitoticity, and Immunity. (ps) (pdf) 30th International Symposium on Mathematical Foundations of Computer Science, Gdansk, Poland, 2005.

  8. C. Glasser, A. Selman, and L. Zhang. Canonical Disjoint NP-Pairs of Propositional Proof Systems. (ps) (pdf) 30th International Symposium on Mathematical Foundations of Computer Science, Gdansk, Poland, 2005.

  9. C. Glasser, A. Pavan, A. Selman, and S. Sengupta. Properties of NP-Complete Sets. (ps) (pdf) 19th IEEE Conference on Computational Complexity, Amherst, MA, June, 2004.

  10. A. Selman and S. Sengupta. Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy. (ps) (pdf) 19th IEEE Conference on Computational Complexity, Amherst, MA, June, 2004.

  11. C. Glasser, A. Selman, and S. Sengupta. Reductions between Disjoint NP-Pairs. (ps) (pdf) 19th IEEE Conference on Computational Complexity, Amherst, MA, June, 2004.

  12. C. Glasser, A. Selman, S. Sengupta, and L. Zhang. Disjoint NP-Pairs. (ps) (pdf) 18th IEEE Conference on Computational Complexity, Aarhus, Denmark, July, 2003.

  13. A. Pavan and A. Selman. Bi-Immunity Separates Strong NP-completeness Notions. (ps) (pdf) 19th International Symposium on Theoretical Aspects of Computer Science, Antibes Juan-les-Pins, France, March, 2002.

  14. A. Pavan and A. Selman. Separaton of NP-completeness notions. (ps) (pdf) SIAM Journal on Computing, 31(3):906--918, 2002.

  15. J. Savage, A. Selman, and C. Smith. History and Contributions of Theoretical Computer Science. (ps) (pdf) In Advances in Computing, ed. M. Zelkowitz, Academic Press, v. 55, 2001.

  16. L. Fortnow, A. Pavan, and A. Selman. Distributionally hard languages. Theory of Computing Systems, 34(3):245--263, 2001.

  17. A. Selman. Much ado about functions. (ps) (pdf) Text of invited address given at the Eleventh IEEE Conference on Computational Complexity, May, 1996.

  18. A. Naik, J. Rogers, J. Royer, and A. Selman. A hierarchy based on output multiplicity. (ps) (pdf) Theoretical Computer Science, 207(1):131--157, 1998.

  19. A. Pavan and A. Selman. Complete distributional problems, hard languages, and resource-bounded measure. (ps) (pdf) Theoretical Computer Science, 234(1--2):273--286, 2000.

  20. A. Naik and A. Selman. Adaptive versus nonadaptive queries to NP and p-selective sets. (ps) (pdf) Computational Complexity, 8(2):171--189, 1999.

  21. J-Y. Cai and A. Selman. Fine separation of average time complexity classes. SIAM Journal on Computing, 28(4):1310--1325, 1999.

  22. S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, and H. Vollmer. Complements of multivalued functions. Chicago Journal of Theoretical Computer Science, March 19, 1999.

ACM Digital Library

ACM DL Author-ize serviceWriting and editing complexity theory: tales and tools
Lane A. Hemaspaandra, Alan L. Selman
ACM SIGACT News, 1998
ACM DL Author-ize serviceStrategic directions in research in theory of computing
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
ACM SIGACT News, 1997
ACM DL Author-ize serviceWide Area Technical Report Service: technical reports online
James C. French, Edward A. Fox, Kurt Maly, Alan L. Selman
Communications of the ACM, 1995
ACM DL Author-ize serviceWide area technical report service‚EUR"technical reports online
Jim French, Edward Fox, Kurt Maly, Alan L. Selman
ACM SIGACT News, 1994
ACM DL Author-ize serviceRelativizing complexity classes with sparse oracles
Timothy J. Long, Alan L. Selman
Journal of the ACM (JACM), 1986
ACM DL Author-ize serviceHard-core theorems for complexity classes
Shimon Even, Alan L. Selmen, Yacov Yacobi
Journal of the ACM (JACM), 1985
ACM DL Author-ize serviceComparison of polynomial-time reducibilities
Richard Ladner, Nancy Lynch, Alan Selman
STOC '74 Proceedings of the sixth annual ACM symposium on Theory of computing, 1974
ACM DL Author-ize serviceTuring machines and the spectra of first-order formulas with equality
Neil D. Jones, Alan L. Selman
STOC '72 Proceedings of the fourth annual ACM symposium on Theory of computing, 1972

Personal

Photos from my trip to Japan, April 1996 (taken by Professor Namiki,TUAT, with his digital camera). Professor Nakamori, TUAT, was my host.

Grandchildren


Send comments: webmaster@@cse.Buffalo.EDU