The
Harvard Theory of Computation Seminar
Spring 2009
General Information
Location:
Talks usually take place in Maxwell
Dworkin (MD), Room 319, 33 Oxford Street, Cambridge. Google
Map.
Time: Talks usually take place on Mondays, with refreshments at 2:30 and talk
at 2:45.
Mailing List: Click here
to receive information about future talks via email.
Previous Years: Click here to see talks from previous
years.
Calendar 
Upcoming
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
Previous
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.