Theory of Computation at Princeton

Theoretical computer science (TCS) studies efficient algorithms and protocols, which ultimately enable much of modern computing. But even more than that, the very concept of computation gives a fundamental new lens for examining the world around us. It underlies many 20th century inventions such as cryptography, computational biology, machine learning, quantum computing, etc. An abiding interest in the power of computation has been a regular feature of life at Princeton since the times of Turing, Church, Goedel and von Neumann (all Princeton residents). The TCS group continues today to pursue research in many areas of theory, including complexity theory, algorithms, data structures, computational geometry, cryptography, machine learning and computational economics. We have close connections with faculty in other groups, including computational biology, graphics, networks and systems.

Princeton is a wonderful place for TCS research. The presence of active research groups at the CS and Math depts, as well as the nearby Institute of Advanced Study (not to mention Rutgers/Dimacs half an hour away) ensures that almost every day there is an exciting talk to go to, or an exciting visitor to meet.

Current Active Areas of Research

  • Algebraic Complexity
  • Algorithmic Game Theory
  • Analysis of Algorithms
  • Analytic Combinatorics
  • Approximation Algorithms
  • Big-Data and Machine Learning
  • Coding Theory
  • Computational Complexity
  • Computational Geometry
  • Data Structures/Network Algorithms
  • Graph Theory
  • Information Theory
  • Natural Algorithms and Dynamical Systems
  • Probabilistically Checkable Proofs/UGC
  • Pseudorandomness
  • Semidefinite Programs