Theory of Computation
at Harvard

People | Research Areas | Positions | Courses

Harvard Theory of Computation Seminar

Faculty and students in the Theory of Computation (Theoretical Computer Science) group aim to

Understand the mathematical laws governing efficient computation, and
Apply this understanding to address problems arising in other parts of computer science and mathematics, and in other fields such as neuroscience and physics.

Faculty

Other Faculty w/TOC interests

Yiling Chen (EconCS)
Noam D. Elkies (Math)
Steven Gortler (Graphics)
David Parkes (EconCS)
Yaron Singer (EconCS, joining Fall 2013)

PhD Students

Mark Bun
Jiayang Jiang
Scott Linderman
Thomas Morgan
Thomas Steinke
Justin Thaler
Jonathan Ullman
Colin Jia Zheng

Postdocs

Tanmoy Chakraborty (CRCS Fellow)
Karthik Chandresekaran (Simons Postdoc)
Brendan Juba
Andrew Wan
Lirong Xia
(CRCS Fellow)

Visitors

Irit Dinur
(Radcliffe Fellow)
Kobbi Nissim
(CRCS Visiting Scholar)

Recent Alumni and Visitors

Varun Kanade (Ph.D. ’12)
Zhenming Liu (Ph.D. ’12)
Tal Moran (CRCS Fellow ’08-‘11)
Brendan Juba (Postdoc ’10-11)
Kai-Min Chung (Ph.D. ’10)
Alex Samorodnitsky (Radcliffe Fellow ’09-‘10)
Jenn Wortman Vaughan (CI Fellow ’09-‘10)
Stephan Holzer (visiting student ’08-’09)
Flavio Chierichetti (visiting student ’08)
Steve Homer (Visiting Faculty ’08)
Adam Kirsch (Ph.D. ’08)
Jin-Yi Cai (Visiting Faculty ’08)
Loizos Michael (Ph.D. ’08)
Yevgeniy Dodis (Visiting Faculty ’08)
Alex Healy (Ph.D. ’07)
Dan Gutfreund (Postdoc & AM Lecturer ’05-’07)
Shien Jin Ong (Ph.D. ’07)

Alon Rosen (CRCS Postdoc ’05-’07)
Vitaly Feldman (Ph.D. ’06)
Emanuele Viola (Ph.D. ’06)
Minh-Huyen Nguyen (Ph.D. ’06)
Eleni Drinea (Ph.D. ’05)
Omer Reingold (CRCS Visiting Scholar, ’05)
David Zuckerman (Radcliffe Fellow, ’04-’05)
Amir Shpilka (Postdoc ’04-’05, joint w/MIT)
Dana Ron (Radcliffe Fellow, ’03-’04)
Madhu Sudan (Radcliffe Fellow, ’03-’04)
Oded Goldreich (Radcliffe fellow, ’03-’04)
Ronitt Rubinfeld (Radcliffe fellow, ’04)
Eli Ben-Sasson (Postdoc ’01-’03)
Adam Klivans (Postdoc ’02-’03)
Rocco Servedio (Ph.D. ’01, Postdoc ’01-’02)
Yan Zhong Ding (Ph.D. ’01)

Research Areas

Design and Analysis of Algorithms: Mitzenmacher, Nelson, Rabin, Valiant
Computational Complexity: Nelson, Vadhan, Valiant
Logic in Computer Science: Lewis
Error-Correcting Codes: Elkies, Mitzenmacher, Vadhan
Cryptography: Rabin, Vadhan
Learning Theory & Cognitive Computation: Valiant
Randomness in Computation: Mitzenmacher, Nelson, Rabin, Vadhan
Quantum Computation: Valiant
Computational Algebra & Number Theory: Elkies, Rabin
Parallel Computation: Rabin, Valiant
Streaming Algorithms: Mitzenmacher, Nelson
Computational Mechanism Design & Game Theory: Chen, Parkes
Data Privacy: Chen, Vadhan
Graphics and Discrete Geometry: Gortler

Positions at Harvard

Theory Group Postdocs: http://toc.seas.harvard.edu/callforapplications-fall2013.html
Computer Science and Applied Math Faculty Positions: http://www.seas.harvard.edu/about-seas/employment/faculty-positions
Postdocs and Lectureships in the math department: http://www.math.harvard.edu/jobs/index.html
Applying for the PhD program: http://www.seas.harvard.edu/audiences/prospective-graduates
Postdoctoral and Visiting Scholar Positions at the Center for Research on Computation and Society (Current foci include “Privacy & Security” and “Economics & Computer Science”): http://crcs.seas.harvard.edu/postdoctoral-fellowship/
Faculty-level Fellowships at the Radcliffe Institute for Advanced Study: http://www.radcliffe.harvard.edu/fellowships/apply.aspx

Courses Related to TOC

Spring 2013

Fall 2012

Past Courses

CS 221. Computational Complexity (Spring 2012)
CS 225. Pseudorandomness (Spring 2011, Next: Spring 2013(?))
CS 228. Computational Learning Theory (Spring 2011, Next: Spring 2014(?))
CS 220r. Cryptography: Trust and Adversity (Fall 2010)
CS 223. Probabilistic Analysis and Algorithms (Fall 2010)
CS 226r. Efficient Algorithms (Fall 2010, Next: ???)
MATH 253. Introduction to Computability and Randomness (Spring 2011, Next: ???)
MATH 162. Introduction to Quantum Computing (Spring 2011, Next: ???)
MATH 298. Random Matrices (Spring 2012)
AM 106/206: Applied Algebra and Combinatorics (Fall 2010, Next: Fall 2013(?))
ES 250. Information Theory (Fall 2010)
ES 210. Mathematical Programming (Fall 2010)
CS 229r. Topics in the Theory of Computation (Biology and Complexity) (Spring 2010, Next: ???)
Additive Combinatorics (Lecturer Ben Green) (Fall 2009, one-time course)
CS 286r. Topics at the Interface between Computer Science and Economics (Assignments, Matching, and Dynamics) (Fall 2009)
MATH 276. Expander Graphs and Number Theory (Spring 2009, Next: ???)

CS 286r. Topics at the Interface between Computer Science and Economics (Social Computing) (Fall 2008)
CS 286r. Topics at the Interface between Computer Science and Economics (Computational Mechanism Design) (Spring 2007)
CS 186. Economics and Computation (Fall 2010)
CS 120. Introduction to Cryptography (Fall 2006, Next: ???)
CS 127. Computational Geometry (Spring 2005, Next: ???)
CS 124. Data Structures and Algorithms (Spring 2012, Next: Spring 2013)
CS 20. Discrete Mathematics for Computer Science (Spring 2012, Next: Spring 2013)
AM 107. Graph Theory and Combinatorics (Spring 2012)
AM 121. Introduction to Optimization: Models and Methods (Spring 2012)
MATH 152. Discrete Mathematics (Fall 2010)
MATH 268x. Graph Limits (Fall 2010)
MATH 270. Advanced Probability Theory (Fall 2010)

Harvard Theory of Computation Seminar