18.408 Topics in Theoretical Computer Science. Fall 2016.
This (graduate level, researchoriented) course will be run as a seminar, with
presentations mostly by the student participants, and several faculty members (Michel Goemans, Ankur Moitra, Jon Kelner, Peter Shor, ...) will participate in some of the sessions. The goal is for the students to present either recent papers from theoretical computer science conferences or more classical results in theoretical computer science that may not be covered in other classes at MIT. The topics covered will depend on the interest of the participants but will likely have an algorithmic slant. The first meeting will be on September 9th at 9AM, and Michel Goemans will be will be giving the first seminar (the remaining ones by students).
Students interested in participating are encouraged to send an email to indicate their interest.
Change of Time and Room. We have moved the seminar to Tuesdays from 11AM to 1PM, and we will meet in 2255.
(Nonexhaustive!) list of possible papers to present:

Kudekar et al., ReedMuller Codes Achieve Capacity on Erasure Channels, STOC 2016.
 Hoberg and Rothvoss, A logarithmic additive integrality gap for bin packing, 2015.

Dwork et al., The Reusable Holdout: Preserving Validity in Adaptive Data Analysis, Science 2015.

Bresler, Efficiently Learning Ising Models on Arbitrary Graphs, STOC 2015.

Valiant, Valiant, An Automatic Inequality Prover and Instance Optimal Identity Testing, FOCS 2014. (Alternatively, DiakonikolasKane simplification.)

Communication complexity of low rank matrices:
 Algorithmic discrepancy:

Bansal, Constructive Algorithms for Discrepancy Minimization, FOCS 2010.

Lovett, Meka, Constructive Discrepancy Minimization by Walking on the Edges, FOCS 2012.
 Rothvoss, Constructive discrepancy minimization for convex sets, 2014.
 Eldan and Singh, Efficient Algorithms for Discrepancy Minimization in Convex Sets, 2014.
 Bansal, Dadush and Garg, An Algorithm for the Komlos Conjecture Matching Banaszczyk's bound, FOCS 2016.
 Bansal et al, Liftandround to improve weighted completion time on unrelated machines, STOC 2016.

Recht, A Simpler Approach to Matrix Completion, JMLR 2011.

Dvir, Gopalan, Yekhanin, Matching Vector Codes, FOCS 2010.

Fenner et al, Bipartite Perfect Matching is in QuasiNC, STOC 2016.
 Alon and Naor, Approximating the CutNorm via Grothendieck's Inequality, SICOMP 2006.

Mossel, O'Donnell, Oleszkiewicz, Noise Stability of Functions with Low Influences: Invariance and Optimality, Annals of Math 2010.

Algorithmic Lovasz Local Lemma:

Batson, Spielman and Srivastava, TwiceRamanujan Sparsifiers, SIAM Review, 2014.
 Marcus, Spielman and Srivastava, Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, Ann. Math, 2015.
 Marcus, Spielman and Srivastava, Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem, Ann. Math 2015.

Raecke, Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC 2008.

Raghavendra, Optimal Inapproximability for Every CSP?, STOC 2008.

Sparsest cut:
 Iterative rounding:

Extended formulations: