Theory of Computation
at Harvard

People | Research | Positions | Courses

Harvard Theory of Computation Seminar (Calendar for 2008-2009)

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	Post-Doc
Harry R. Lewis Michael Mitzenmacher David Parkes Michael O. Rabin Salil Vadhan Leslie G. Valiant Noam D. Elkies (Math Dept)	Flavio Chierichetti (visiting from La Sapienza) Kai-Min Chung Stephan Holzer (visiting from TU Munich) Shaili Jain Zhenming Liu Jia Zheng			Tal Moran (CRCS postdoc)

Recent Alumni and Visitors

Steve Homer (Visiting Faculty ’08) Adam Kirsch (Ph.D. ’08) Jin-Yi Cai (Visiting Faculty ’08) Alex Healy (Ph.D. ’07) Dan Gutfreund (Postdoc & AM Lecturer ’05-’07) Vitaly Feldman (Ph.D. ’06) Emanuele Viola (Ph.D. ’06) Omer Reingold (CRCS Visiting Scholar, ’05) David Zuckerman (Radcliffe Fellow, ’04-’05) Dana Ron (Radcliffe Fellow, ’03-’04) Madhu Sudan (Radcliffe Fellow, ’03-’04) Adam Klivans (Postdoc ’02-’03) Yan Zhong Ding (Ph.D. ’01)

Loizos Michael (Ph.D. ’08) Yevgeniy Dodis (Visiting Faculty ’08) Shien Jin Ong (Ph.D. ’07) Alon Rosen (CRCS Postdoc ’05-’07) Minh-Huyen Nguyen (Ph.D. ’06) Eleni Drinea (Ph.D. ’05) Amir Shpilka (Postdoc ’04-’05, joint w/MIT) Oded Goldreich (Radcliffe fellow, ’03-’04) Ronitt Rubinfeld (Radcliffe fellow, ’04) Eli Ben-Sasson (Postdoc ’01-’03) Rocco Servedio (Ph.D. ’01, Postdoc ’01-’02)

---

Research Areas

• Design and Analysis of Algorithms: Mitzenmacher, Rabin, Valiant
• Computational Complexity: Vadhan, Valiant
• Logic in Computer Science: Lewis
• Error-Correcting Codes: Elkies, Mitzenmacher
• Cryptography: Rabin, Vadhan
• Learning Theory & Cognitive Computation: Valiant
• Randomness in Computation: Mitzenmacher, Rabin, Vadhan
• Quantum Computation: Valiant
• Computational Algebra & Number Theory: Elkies, Rabin
• Parallel Computation: Rabin, Valiant
• Computational Mechanism Design & Game Theory: Parkes

---

Positions at Harvard

• Computer Science Faculty Positions: http://www.eecs.harvard.edu/index/eecs_jobs.php.
• Graduate study (S.M. and Ph.D.)
• Theory Group Postdocs: Occasionally, we have postdoc positions available. If you are interested in such a position, e-mail theory-postdoc-app@eecs.harvard.edu with a CV, research statement, and a list of three references.
• Postdocs & Visiting Scholar Positions at the Center for Research on Computation and Society: Current foci include "Privacy & Security".
• Applied Math Lectureships: TBD
• Computer Science Faculty Positions: TBD
• Faculty-level Fellowships at the Radcliffe Institute for Advanced Study
• Benjamin Peirce Lectureships in the Math Dept

---

Courses Related to TOC

Fall 2008

• CS 121: Introduction to Formal Systems and Computation
• CS 226r: Efficient Algorithms
• CS 286r: Topics at the Interface between Computer Science and Economics (Social Computing)

Spring 2009

• CS 124: Data Structures and Algorithms
• CS 225: Pseudorandomness
• CS 228: Computational Learning Theory
• AM 107: Graph Theory and Combinatorics
• MATH 276 Expander Graphs and Number Theory

Past Courses

• CS 221: Computational Complexity (Spring 2008)
• CS 124: Data Structures and Algorithms (Spring 2008)
• CS 221: Computational Complexity (Spring 2007)
• CS 120: Introduction to Cryptography
• CS 220r: Cryptography: Trust and Adversity (Fall 2006)
• CS 222: Algorithms at the Ends of the Wire (Fall 2006)
• AM 106: Applied Algebra and Combinatorics (Fall 2006)
• CS 127: Computational Geometry (Spring 2005)

---

Harvard Theory of Computation Seminar