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

  • 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.
  • Goldfeld Ziv Goldfeld: Information theory, mathematical statistics, optimal transport, and statistical learning theory.
  • halpern Joe Halpern: Reasoning about knowledge and uncertainty, distributed computing, causality, security, game theory.
  • hopcroft John Hopcroft: Algorithms, information capture and access, random graphs and spectral methods.
  • Michael P. Kim: Foundations of responsible machine learning, algorithmic fairness, learning theory.
  • 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.
  • pass Thomas Ristenpart: Cryptography, computer security, technology abuse.
  • shmoys David Shmoys: Approximation algorithms, computational sustainability.
  • Sridharan Karthik Karthik Sridharan: Theoretical machine learning.
  • stephens-davidowitz Noah Stephens-Davidowitz: Theory, lattices, geometry, cryptography.
  • sun Wen Sun: Theoretical Reinforcement Learning and Machine Learning.
  • tardos Eva Tardos: Algorithms, algorithmic game theory.
  • williamson David Williamson: Approximation algorithms, information networks.
  • lee yu Christina Lee Yu: Algorithms, high dimensional statistics, sequential decision making, machine learning.
  • van zuylen Anke van Zuylen: Algorithms, combinatorial optimization.

 

Courses

Course
Last offered
Instructor(s)
CS 2800: Discrete Structures Fall '21* F. Schalekamp, A. Silva

CS 2802: Discrete Structures - Honors

Spring '20 J. Halpern
CS 2850: Networks Fall '21 D. Easley, J. Halpern
CS 4810: Intro to Theory of Computing Fall '19* J. Hopcroft
CS 4812: Quantum Information Processing Fall '21 P. Ginsparg
CS 4814: Introduction to Computational Complexity Spring '21 E. Chattopadhyay
CS 4820: Introduction to Algorithms Spring '21* B. Kleinberg
CS 4830: Introduction to Cryptography Spring '21* N. Stephens-Davidowitz
CS 4850: Mathematical Foundations
for the Information Age
Spring '20* J. Hopcroft
CS 4852: Networks II: Market Design Spring '19* A. Ghosh
CS 4860: Applied Logic Fall '20 R. Constable
CS 5820: Analysis of Algorithms Fall '21* A. van Zuylen
CS 5830: Introduction to Cryptography Spring '18* R. Pass
CS 5846: Decision Theory I Spring '21 J. Halpern, L. Blume
CS 5850: Mathematical Foundations for the Information Age Spring '21* B. Kleinberg
CS 5854: Networks and Markets Spring '21 R.Pass
CS 6764: Reasoning About Knowledge Fall '18* J. Halpern
CS 6766: Reasoning About Uncertainty Fall '19 J. Halpern
CS 6783: Machine Learning Theory Fall '21 K. Sridharan
CS 6789: Foundations of Reinforcement Learning Fall '20 W. Sun
CS 6802: Lattices: Geometry, Cryptography, and Algorithms Fall '21 N. Stephens-Davidowitz
CS 6810: Theory of Computing Fall '21 E. Chattopadhyay
CS 6815: Pseudorandomness and Combinatorial Constructions Fall '19 E. Chattopadhyay
CS 6817: Special Topics in Complexity Theory Fall '20 E. Chattopadhyay
CS 6820: Analysis of Algorithms Fall '21 R. Kleinberg
CS 6830: Cryptography Fall '20 N. Stephens-Davidowitz
CS 6840: Algorithmic Game Theory Spring '20 É. Tardos
CS 6850: The Structure of Information Networks Fall '21 J. Kleinberg
CS 6860: Logics of Programs Spring '21 R. Constable
CS 6861: Introduction to Kleene Algebra Fall '19 D. Kozen
ORIE 6300: Mathematical Programming I Fall '21 A. Lewis
ORIE 6330: Graph Theory and Network Flows Fall '20 D. Williamson
ORIE 6334: Combinatorial Optimization Fall '19* D. Williamson

* offered Spring '22