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.


  • Jayadev AcharyaJayadev Acharya: Information theory, machine learning, and algorithmic statistics.
  • Siddhartha BanerjeeSiddhartha Banerjee: Stochastic Modeling, Design of Scalable Algorithms, Matching Markets and Social Computing, Control of Information-Flows, Learning and Recommendation.
  • Eshan ChattopadhyayEshan Chattopadhyay : Randomness and Computation, Computational Complexity theory, Cryptography.
  • constable Robert Constable: Type theory and automated reasoning.
  • halpern Joe Halpern: Reasoning about knowledge and uncertainty, distributed computing, causality, security, game theory.
  • hartmanis Juris Hartmanis: Computational complexity theory.
  • hopcroft John Hopcroft: Algorithms, information capture and access, random graphs and spectral methods.
  • bkleinberg Bobby Kleinberg: Algorithms, game theory, learning, and networks.
  • jkleinberg Jon Kleinberg: Algorithms, social and information networks.
  • kozen Dexter Kozen: Computational complexity, program logic and semantics, computational algebra.
  • pass Rafael Pass: Cryptography and its interplay with computational complexity and game theory.
  • shmoys David Shmoys: Approximation algorithms, computational sustainability.
  • Sridharan Karthik Karthik Sridharan: Theoretical machine learning.
  • stephens-davidowitz Noah Stephens-Davidowitz: Theory, lattices, geometry, cryptography.
  • tardos Eva Tardos: Algorithms, algorithmic game theory.
  • 20160820_udell_crop Madeleine Udell: Optimization and machine learning for large scale data analysis and control.
  • williamson David Williamson: Approximation algorithms, information networks.



CS 2800: Discrete Structures Sring 2017(M. George)
CS 2850: Networks Fall 2016 (D. Easley, E. Tardos)
CS 4810: Intro to Theory of Computing Spring 2016 (D. Kozen)
CS 4812: Quantum Information Processing Fall 2016 (P. Ginsparg)
CS 4814: Introduction to Computational Complexity Fall 2015 (D. Steurer)
CS 4820: Introduction to Algorithms Spring 2017 (B. Kleinberg and F. Schalekamp)
CS 4830: Introduction to Cryptography Spring 2017 (E. Shi)
CS 4850: Mathematical Foundations
for the Information Age
Spring 2017 (J. Hopcroft)
CS 4860: Applied Logic Fall 2016 (R. Constable)
CS 5786: Machine Learning for Data Science Fall 2016 (K. Sridharan)
CS 5830: Introduction to Cryptography Spring 2017 (R. Pass)
CS 5846: Decision Theory I Spring 2017 (j. Halpern)
CS 5854: Networks and Markets Fall 2016 (R.Pass)
CS 5860: Intro to Formal Methods Fall 2014 (R. Constable)
CS 6764: Reasoning About Knowledge Spring 2015 (J. Halpern)
CS 6766: Reasoning About Uncertainty Fall 2015 (J. Halpern)
CS 6783: Machine Learning Theory Fall 2015 (K. Sridharan)
CS 6810: Theory of Computing Spring 2017 (D. Kozen)
CS 6820: Analysis of Algorithms Fall 2016 (R. Kleinberg)
CS 6825: The Science Base for the Information Age Fall 2014 (J. Hopcroft)
CS 6830: Cryptography Spring 2017 (R. Pass)
CS 6832: Applied Cryptography Fall 2016 (E. Shi)
CS 6840: Algorithmic Game Theory Spring 2017 (É. Tardos)
CS 6850: The Structure of Information Networks Spring 2017 (J. Kleinberg)
CS 6860: Logics of Programs Fall 2015 (D. Kozen)
ORIE 6334: Combinatorial Optimization Fall 2016 (D. Williamson)
ORIE 6335: Design and Analysis of Scheduling Algorithms Fall 2014 (D. Shmoys)