The theory of computing is the study of efficient computation, models of computational processes, and their limits. 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. In keeping with our tradition of opening new frontiers in theory research, we have emerged in recent years as a leader in exploring the interface between computation and the social 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

  • Robert Constable: Type theory and automated reasoning.
  • Arpita Ghosh: Algorithms and mechanism design in the context of strategic behavior on the Web. Markets and mechanisms for privacy.
  • Joe Halpern: Reasoning about knowledge and uncertainty, distributed computing, causality, security, game theory.
  • Juris Hartmanis: Computational complexity theory.
  • John Hopcroft: Algorithms, information capture and access, random graphs and spectral methods.
  • Bobby Kleinberg: Algorithms, game theory, learning, and networks.
  • Jon Kleinberg: Algorithms, social and information networks.
  • Dexter Kozen: Computational complexity, program logic and semantics, computational algebra.
  • Rafael Pass: Cryptography and its interplay with computational complexity and game theory.
  • David Shmoys: Approximation algorithms, computational sustainability.
  • Karthik Sridharan: Theoretical machine learning.
  • David Steurer: Algorithms and complexity theory, hardness of approximation, SDP rounding.
  • Eva Tardos: Algorithms, algorithmic game theory.
  • David Williamson: Approximation algorithms, information networks.

 

Courses

CS 2800: Discrete Structures Fall 2014 (S. Chaudhuri and M. George)
CS 2850: Networks Fall 2014 (D. Easley, J. Kleinberg)
CS 4810: Intro to Theory of Computing Fall 2013 (D. Steurer)
CS 4812: Quantum Information Processing Spring 2014 (P. Ginsparg)
CS 4820: Introduction to Algorithms Spring 2014 (B. Kleinberg and D. Steurer)
CS 4850: Mathematical Foundations
for the Information Age
Spring 2014 (J. Hopcroft)
CS 4860: Applied Logic Fall 2012 (R. Constable)
CS 5830: Introduction to Cryptography Fall 2013 (R. Pass)
CS 5860: Intro to Formal Methods Fall 2014 (R. Constable)
CS 6764: Reasoning About Knowledge Spring 2012 (J. Halpern)
CS 6766: Reasoning About Uncertainty Spring 2013 (J. Halpern)
CS 6783: Machine Learning Theory Fall 2014 (K. Sridharan)
CS 6810: Theory of Computing Fall 2012 (D. Steurer)
CS 6820: Analysis of Algorithms Fall 2014 (É. Tardos)
CS 6830: Cryptography Fall 2014 (R. Pass)
CS 6840: Algorithmic Game Theory Spring 2014 (É. Tardos)
CS 6850: The Structure of Information Networks Fall 2013 (J. Kleinberg)
CS 6860: Logics of Programs Fall 2010 (D. Kozen)
ORIE 6334: Approximation Algorithms Spring 2014 (D. Williamson)
ORIE 6335: Design and Analysis of Scheduling Algorithms Fall 2014 (D. Shmoys)