**Meeting:** Thursdays, 1:30pm-4pm, GHC 4303

**Instructor:** Ryan
O'Donnell

**Course Blog:** http://theory-hits09.blogspot.com/

**Overview:** This is a graduate-level seminar class covering great
papers in theoretical computer science from 2009 (and 2010). Each week,
one student will present one of the papers to the class. The goal is to
show complete proof details for the main results in the paper, to the
extent that this is possible in a 1.5 to 2.5 hour talk. Prior to their
presentations, the students will also be responsible for a blog posting
giving basic background info and motivation for the paper. In addition to
learning about recent results, a goal of this course is to stimulate
further research on open problems related to the paper.

**Schedule:**

Jan. 28 | Shiva | [CGH] | Deterministic algorithms for the Lovász Local Lemma |

Feb. 4 | Aaron | [DobDug] | On the power of randomization in algorithmic mechanism design |

Feb. 11 | Richard | [BSS] | Twice-Ramanujan sparsifiers |

Feb. 18 | Zed | [KLPT] | Higher eigenvalues of graphs |

Feb. 25 | Ravi | [AGMOS] | An O(log n / log log n)-approximation algorithm for the asymmetric traveling salesman problem |

Mar. 4 | Ryan away | No class | |

Mar. 11 | Spring Break | No class | |

Mar. 18 | Ali | [DinHar] | Composition of low-error 2-query PCPs using decodable PCPs |

Mar. 25 | Or | [Roughgarden] | Intrinsic robustness of the price of anarchy |

Apr. 1 | Yi | [Gentry] | Fully homomorphic encryption using ideal lattices |

Apr. 8 | Yuan | [Braverman] | Poly-logarithmic independence fools
AC^{0} circuits |

Apr. 15 | Srivatsan | [BanWil] | Regularity lemmas and combinatorial algorithms |

Apr. 22 | Pranjal | [Sherstov] | The intersection of two halfspaces has high threshold degree |

Apr. 29 | Harsha | [LLW] | Tight bounds for clock synchronization |

Below are some additional great hits from theoretical computer science in 2009. If anyone else is interested in giving a talk (at a nonstandard time), they might want to choose from this list: