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

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

• CSE 191 Discrete Structures

Recent Activities

• Editor-in-Chief, Theory of Computing Systems, 2001--
• Chaired the NSF-Sponsored Workshop on Research in Theoretical Computer Science, March 1999; see link above for final report
• Books
  • Essays in Memory of Shimon Even (Goldreich, Rosenberg, and Selman, eds.)
  • Complexity Theory Retrospective II (Hemaspaandra and Selman, eds.)
  • Complexity Theory Retrospective
• Member of the Editorial Board
  • Journal of Computer and System Sciences
  • Chicago Journal of Theoretical Computer Science
• Member of the Working Group, Theory of Computing, ACM Workshop on Strategic Directions in Computing Research, June 1996, and co-author of the report, Strategic Directions for Research in Theory of Computing

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.

    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