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

PhD Students

Visitors / Post-doc

Tanmoy Chakraborty (CRCS Fellow)
Lirong Xia (CRCS Fellow)

Recent Alumni and Visitors

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
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: Parkes

Positions at Harvard

Theory Group Postdocs: http://toc.seas.harvard.edu/callforapplications-fall2012.html
Computer Science and Applied Math Faculty Positions: http://www.seas.harvard.edu/csjobs/
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
Post-doctoral 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

Fall 2010

Spring 2012

Past Courses

CS 225. Pseudorandomness (Spring 2011, Next: Spring 2013(?))
CS 228. Computational Learning Theory (Spring 2011, Next: Spring 2014(?))
MATH 253. Introduction to Computability and Randomness (Spring 2011, Next: ???)
MATH 162. Introduction to Quantum Computing (Spring 2011, Next: ???)
CS 222. Algorithms at The End of the Wire (Fall 2010, Next: Fall 2012(?))
CS 226r. Efficient Algorithms (Fall 2010, Next: ???)
CS 286r. Topics at the Interface between Computer Science and Economics (Information, Prediction, and Collective Intelligence) (Fall 2010)
AM 106/206: Applied Algebra and Combinatorics (Fall 2010, Next: Fall 2013(?))
ES 250. Information Theory (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 120. Introduction to Cryptography (Fall 2006, Next: ???)
CS 127. Computational Geometry (Spring 2005, Next: ???)

Harvard Theory of Computation Seminar