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, *Dynamics,
Equilibrium Selection and Network Structure*

Monday, September 29, 2008 *Gossiping
in Social Networks*

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

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

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

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

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

Monday, April 23, 2:30pm. 2007 Phil Klein, *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, *Efficient Distributed Approximation Algorithms
for Minimum Spanning Trees*

Monday, February 26, 2:30pm. 2007 Shanghua Teng, *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.