The Harvard Theory of Computation Seminar


General Information

Location: Maxwell Dworkin 323.
Time: Usually Wednesdays at 12 noon (over lunch).
Mailing List: Click here to receive information about future talks via email.
Previous Years: Click here to see talks from previous years.



Wednesday, September 23, 2009, Justin Thaler Graph Covers and Quadratic Minimization

Friday, October 9, 2009, (Pierce Hall 100F at 3:00PM, Joint TOC-PL talk) Harvey M. Friedman Decision Procedures for Verification


Friday, Feb 20, 2009, David Xiao On the Black-box Complexity of PAC Learning

Monday, Feb 23, 2009, Zhenming Liu Designing Floating Codes for Expected Performance

Thursday, Feb 26, 2009, Muthu Muthukrishnan See the departmental colloquium series

Wednesday, March 11, 2009 Ketan Mulmuley On P vs NP, Geometric Complexity, and the Riemann Hypothesis

Monday, March 30, 2009 David Choi Sample Complexity Bounds for Link Prediction

Monday, April 6th, 2009 Alex Slivkins Multi-Armed Bandits in Metric Space

Wednesday, April 15th, 2009, Katrina Ligett Differentially private approximation algorithms

Monday April 20th, 2009 Alex Samorodnitsky Counting Magic Squares

Wednesday April 29th 2009 Guy Rothblum On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results (CRCS Privacy and Security Lunch Seminar)

Thursday April 30th 2009 Jennifer Chayes IIC/CS colloquium

Monday, December 8, 2008,  Yuri Gurevich Proof of Church’s Thesis

Monday, December 1, 2008, Luca Trevisan Regularity, boosting, and efficiently simulating every high entropy distribution

Monday, November 10, 2008, Kai-Min Chung Tight Bounds for Hashing Block Sources

Monday, November 3, 2008, Ran Raz Parallel Repetition of Two Prover Games: A Survey, Application, and a Counterexample to Strong Parallel Repetition.

Monday, October 20, 2008 Tal Moran An Optimally Fair Coin Toss: Cleve’s Bound is Tight

Monday, October 6 (Joint TOC/EconCS Seminar), Amin Saberi, Stanford University, Game Dynamics, Equilibrium Selection and Network Structure

Monday, September 29, 2008 Flavio Chierichetti  Sapienza University of Rome Gossiping in Social Networks

Monday, September 15. Alan Frieze, Carnegie Mellon University Finding a Maximum Matching in a Sparse Random Graph in $O(n)$ Expected Time

Monday, May 14, 2:30pm 2007. Allan Borodin, University of Toronto & IAS. Greedy algorithms and other simple greedy-based algorithms for simple (to define) optimization problems

Monday, May 7, 2:30pm 2007. Lenore Cowen, Tufts University. Compact Routing from Theory to Practice

Thursday, May 3, 2007, 4pm (CS Colloquium Series). Ramin Zabih, Cornell University. Flow-based optimization methods in computer vision

Monday, April 30, 2:30pm. 2007 Ueli Maurer, ETH Zurich. Indistinguishability Amplification

Monday, April 23, 2:30pm. 2007 Phil Klein, Brown University. A planar-graph decomposition, and its application to TSP and Steiner Tree

Monday, April 16, 2:30pm. 2007 Sergey Yekhanin, MIT. New Locally Decodable Codes and Private Information Retrieval Schemes

Monday, April 2, 2:30pm. 2007 Martin Wainwright, UC Berkeley. Analysis of MAX-XORSAT and its Generalizations, with Application to Distributed Compression and "Dirty Paper" Coding

Monday, March 12, 2:30pm. 2007 Gopal Pandurangan, Purdue University. Efficient Distributed Approximation Algorithms for Minimum Spanning Trees

Monday, February 26, 2:30pm. 2007 Shanghua Teng, Boston University and Akamai Technologies. Game and Market Equilibria

Monday, February 12, 2:30pm. 2007 Ankit Patel, Harvard. The Theory of Desynchronization: Self-Organizing Algorithms for Periodic Resource Scheduling

Monday, February 5, 2:30pm. 2007 Salil Vadhan, Harvard. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes

Calendar for Computer Science Colloquium Series can be found here.

Calendar for CRCS Privacy & Security Lunch Seminars can be found here.

Previous Talks

Fall 2006
Spring 2006