Theory of Computing

The theory of computing is the study of efficient computation, models of computational processes, and their limits. It has emerged over the past few decades as a deep and fundamental scientific discipline.

It is a young science, with many of the central questions still unanswered; and it is a science poised to have considerable impact on current issues in the development of systems and software, the nation's network and communications infrastructure, and the physical and biological sciences. At Cornell, we are proud of our position as a world leader in the on-going development of theoretical computer science.

Research at Cornell spans all areas of the theory of computing and is responsible for the development of modern computational complexity theory, the foundations of efficient graph algorithms, and the use of applied logic and formal verification for building reliable systems. Our faculty and students are actively involved in areas such as the design of fundamental algorithms, combinatorial optimization, machine learning, computational complexity theory, computational algebra, logic in computer science, computational geometry, and applications to verification, reliable systems, multimedia and image processing, and the computational sciences.

In addition to its depth in the central areas of theory, Cornell is unique among top research departments in the fluency with which students can interact with faculty in both theoretical and applied areas, and work on problems at the critical juncture of theory and applications.

Faculty and Researchers

Paul Chew works in the field of computational geometry with an emphasis on practical applications. These applications have included placement, motion planning, shape comparison, vision, sensing, mesh generation, and lately, matching of molecules.

Robert Constable works on type theory and automated reasoning. Automated reasoning is an inexhaustible source of fascinating problems in logic and computing theory. He received a Guggenheim Fellowship in 1992.

Joe Halpern works on reasoning about knowledge and uncertainty, and its applications to distributed computing, artificial intelligence, and game theory. He has also done work in, and remains interested in, fault tolerance, modal logic, and program verification. He is a AAAI fellow and received the Godel Prize in 1997.

Juris Hartmanis works on computational complexity theory. He is interested in what makes problems hard to compute, techniques to verify degrees of hardness, and what is the best that can be done with computational resources that are insufficient to solve a problem. He is a member of the National Academy of Engineering and the National Research Council Computer Science and Telecommunications Board, and he received the ACM Turing Award in 1993. He previously served as the Assistant Director of NSF for Computer and information Sciences and Engineering.

John Hopcroft works in the area of algorithms and information capture and access. His interests include large random graphs, spectral analysis, dimension reduction and clustering. He is a member of the National Academy of Engineering and the National Research Council Board on Mathematical Sciences and Applications. He received the ACM Turing Award in 1986 and previously was a Presidential appointee to the National Science Board overseeing the National Science Foundation.

Bobby Kleinberg works on topics including economic aspects of algorithms, online learning and its applications, and optimization problems in network routing. He has received an NSF Mathematical Sciences Postdoctoral Research Fellowship, and prior to this has also worked for Akamai Technologies, developing technologies for Internet mapping and streaming media content delivery.

Jon Kleinberg works on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. He is the recipient of an NSF Career Award, an ONR Young Investigator Award, research fellowships from the MacArthur, Packard, and Sloan Foundations, the Rolf Nevanlinna Prize from the International Mathematical Union, and the National Academy of Sciences Award for Initiatives in Research.

Dexter Kozen works on computational complexity, especially the complexity of decision problems in logic and algebra, program logic and semantics, and computational algebra. He received a Guggenheim Fellowship in 1991.

Rafael Pass works on cryptography and its interplay with computational complexity (and game theory), and has contributed to the foundations of concurrent protocols for secure computation.

David Shmoys works on the design and analysis of algorithms, focusing on algorithms for combinatorial optimization problems, including problems in scheduling, network design and location theory. He received a Presidential Young Investigator award in 1987.

Eva Tardos works on the design and analysis of algorithms for problems on graphs or networks. She is most known for her work on network-flow algorithms and approximation algorithms for network problems. Her recent work focuses on algorithmic game theory, an emerging area concerned with designing systems and algorithms for selfish users. She received the Fulkerson Prize in 1988,a Packard Fellowship in 1990, a Presidential Young Investigator award in 1991, a Sloan Fellowship in 1992, a Guggenheim Fellowship in 1999, and the Dantzig Prize in 2006. She is a Fellow of the ACM and the American Academy of Arts and Sciences.

David Williamson works in the area of the design and analysis of algorithms, with an emphasis on algorithms for approximately solving problems in combinatorial optimization. His work has included algorithms for network design, facility location, satisfiability, and finding large cuts in graphs. He received the Tucker Prize in 1994, the SIAM DiPrima Prize in 1996, the SIAM Optimization Group Prize in 1999, and the AMS-MPS Fulkerson Prize in 2000.