15-859U: Theoretical Computer Science's Greatest Hits, 2009

Spring 2010, 12 units

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⁰ 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:

[Peikert] Public-key cryptosystems from the worst-case Shortest Vector Problem (Cryptography, learning theory)

[BDFKMPSSU] Inapproximability for VCG-based combinatorial auctions (Algorithmic game theory, complexity theory)

[BarKoz] Constraint satisfaction problems of bounded width (Algorithms, algebra)

[Efremenko] 3-query locally decodable codes of subexponential length (Coding theory)

[Thomasse] A 4k^2 kernel for Feedback Vertex Set (Algorithms, fixed parameter tractability)

[RagSte] How to round any CSP (Approximation algorithms)

[Sherman] Breaking the multicommodity flow barrier for O(sqrt{log n})-approximations to Sparsest Cut (Approximation algorithms)

[Trevisan] Max Cut and the smallest eigenvalue (Approximation algorithms, spectral graph theory)

[Rossman] The monotone complexity of k-Clique on random graphs (Circuit complexity)

[ABBG] Computational complexity and information asymmetry in financial products (Complexity theory)

[AES] Small-size epsilon-nets for axis-parallel rectangles and boxes (Computational geometry)

[Chazelle] The convergence of bird flocking (Computational geometry, spectral algorithms)

[Feldman] Distribution-specific agnostic boosting (Learning theory)

[HKZ] A spectral algorithm for learning Hidden Markov Models (Learning theory)

[CKN] A (log n)^Omega(1) integrality gap for the Sparsest Cut SDP (Metric embeddings)

[JJUW] QIP = PSPACE (Quantum computation, parallel algorithms)

[Coja-Oghlan] A better algorithm for random k-SAT (SAT algorithms, statistical physics)

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⁰ 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

[Peikert]	Public-key cryptosystems from the worst-case Shortest Vector Problem	(Cryptography, learning theory)
[BDFKMPSSU]	Inapproximability for VCG-based combinatorial auctions	(Algorithmic game theory, complexity theory)
[BarKoz]	Constraint satisfaction problems of bounded width	(Algorithms, algebra)
[Efremenko]	3-query locally decodable codes of subexponential length	(Coding theory)
[Thomasse]	A 4k^2 kernel for Feedback Vertex Set	(Algorithms, fixed parameter tractability)
[RagSte]	How to round any CSP	(Approximation algorithms)
[Sherman]	Breaking the multicommodity flow barrier for O(sqrt{log n})-approximations to Sparsest Cut	(Approximation algorithms)
[Trevisan]	Max Cut and the smallest eigenvalue	(Approximation algorithms, spectral graph theory)
[Rossman]	The monotone complexity of k-Clique on random graphs	(Circuit complexity)
[ABBG]	Computational complexity and information asymmetry in financial products	(Complexity theory)
[AES]	Small-size epsilon-nets for axis-parallel rectangles and boxes	(Computational geometry)
[Chazelle]	The convergence of bird flocking	(Computational geometry, spectral algorithms)
[Feldman]	Distribution-specific agnostic boosting	(Learning theory)
[HKZ]	A spectral algorithm for learning Hidden Markov Models	(Learning theory)
[CKN]	A (log n)^Omega(1) integrality gap for the Sparsest Cut SDP	(Metric embeddings)
[JJUW]	QIP = PSPACE	(Quantum computation, parallel algorithms)
[Coja-Oghlan]	A better algorithm for random k-SAT	(SAT algorithms, statistical physics)