Dexter Kozen
Joseph Newton Pew, Jr. Professor of Engineering
kozen@cs.cornell.edu
http://www.cs.cornell.edu/kozen/
PhD Cornell, 1977
My research interests include the theory of computational
complexity, especially complexity of decision problems in logic and algebra, program logic
and semantics, and computational algebra. Recent work includes: new polynomialtime
algorithms for type inference in type systems with subtypes and recursive types;
algorithms solving systems of set constraints as used in program analysis; a unification
algorithm for set constraints and a new constraint logic programming language based on set
constraints; development of the theory of rational spaces 

and their relationship to set constraints;
an algorithm for decomposition of algebraic functions; a new polynomialtime algorithm for
resolution of singularities of plane curves; efficient algorithms for optimal transmission
of encoded video data; optimality results for digital interleavers; and complexity and
completeness results for Kleene algebras with tests. Recently I have begun to investigate
the application of Kleene algebra and the modal mucalculus to problems in software
security. 
University Activities
Undergraduate Admissions Committee, College of
Engineering
University Arbitration Panel
Faculty Advisor: Cornell Men's Rugby Football Club
and Johnson Graduate School of Management Rugby Football Club
Professional Activities
Program Committees: IEEE Symp. Found. Computer
Science (FOCS), 1996; Fixpoints in Computer Science, Sept. 1998
Supervisory Board: Centre for Basic Research in
Computer Science (BRICS), Aarhus Univ. Organizing Committee: IEEE Symp. Logic in Computer
Science (LICS)
Organizing Committee: Dagstuhl Seminar on Tree
Automata, Oct. 1997
Publications
On the complexity of reasoning in Kleene algebra. Proc.
12th Symp. Logic in Computer Science (LICS), Los Alamitos, CA. (June 1997), 195202.
Efficient algorithms for optimal video
transmission. Proc. IEEE Data Compression Conf. (DCC'98), (J.A. Storer and M. Cohn
ed.), (March 1998), 229238 (with Y. Minsky and B. Smith).
Set constraints and logic programming. Information
and Computation 141, 1 (April 1998), 225.
