Dexter Kozen
Joseph Newton Pew Jr. Prof. of Engineering
PhD Cornell University, 1977
My research interests include the theory of computational complexity,
especially complexity of decision problems in logic and algebra, and logics
and semantics of programming languages. Recent work includes new
polynomial-time algorithms and deductive systems for type inference and
solutions of set constraints; a new algorithm for decomposition of
algebraic functions; a new polynomial-time algorithm for resolution of
singularities of plane curves; and new polynomial-time algorithms for
optimal transmission of encoded video data.
University Activities
- College of Engineering Undergraduate Admissions Committee
Professional Activities
- Program Committees: IEEE Symposium Logic in Computer Science,
1995 (chair); Scandinavian Workshop on Algorithm Theory, 1994
- Organizing Committee, Symposium in Honor of Juris Hartmanis and
Richard Stearns, Albany, 1994
- Supervisory Board, Centre for Basic Research in Computer Science
(BRICS), Aarhus University, Denmark
Invited Lectures
- Set constraints and logic programming. First Conference Constraints
in Computational Logics (CCL'94), Munich, September 1994.
- Efficient resolution of singularities of plane curves. 14th Conference
Foundations of Software Technology and Theoretical Computer
Science, Madras, India, December 1994.
- Rational spaces and set constraints. Sixth International Joint
Conference on the Theory and Practice of Software Development
(TAPSOFT'95), Aarhus, Denmark, May 1995.
Publications
- Optimal bounds for the change-making problem. Theoretical Computer
Science 123 (1994), 377-388 (with Shmuel Zaks).
- A completeness theorem for Kleene algebras and the algebra of regular
events. Information and Computation 110, 2 (May 1994), 366-390.
- Efficient inference of partial types. Journal of Computing System Science
49, 2 (October 1994), 306-324 (with Jens Palsberg and Michael I.
Schwartzbach).
- Efficient recursive subtyping. Mathematical Structures in Computer
Science 5, (1995),1-13 (with Jens Palsberg and Michael I. Schwartzbach).
- Efficient average-case algorithms for the modular group. Proceedings of
the 35th Symposium Foundations Computer Science, IEEE, (November
1994), 143-152 (with Jin-Yi Cai, W. H. J. Fuchs, and Zicheng Liu).
- Efficient resolution of singularities of plane curves. Proceedings of
the 14th Conference on Foundations of Software Technology and
Theoretical Computer Science, Lecture Notes in Computer Science 880,
Springer-Verlag, (December 1994), 1-11.
- Set constraints and logic programming. Proceedings of the First Conference
on Constraints in Computational Logics (CCL'94) Lecture Notes in
Computer Science 845, ESPRIT, Springer-Verlag, (September 1994), 302-303.
- Rational spaces and set constraints. Proceedings of the Sixth International
Joint Conference on the Theory and Practice of Software Development
(TAPSOFT'95), Lecture Notes in Computer Science 915, Springer-Verlag,
(May 1995), 42-61.
- Decomposition of algebraic functions. Proceedings of the First
Algorithmic Number Theory Symposium (ANTS), Lecture Notes in
Computer Science 877. Mathematical Sciences Institute,
Springer-Verlag, (May 1994), 80-92 (with Susan Landau and Richard Zippel).
Return to:
1994-1995 Annual Report Home Page
-
Departmental Home Page
If you have questions or comments please contact:
www@cs.cornell.edu.
Last modified: 24 November 1995 by Denise Moore
(denise@cs.cornell.edu).
