18.408 Topics in Theoretical Computer Science. Fall 2016.

This (graduate level, research-oriented) 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 2-255.

(Non-exhaustive!) list of possible papers to present:

• Kudekar et al., Reed-Muller 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, Diakonikolas-Kane simplification.)
• Communication complexity of low rank matrices:
  • Lovett, Communication is Bounded by the Root of Rank, STOC 2014.
  • Or Rothvoss, A direct proof for Lovett's bound on the coomunication complexity of low rank matrices, 2014.
• 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, Lift-and-round 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 Quasi-NC, STOC 2016.
• Alon and Naor, Approximating the Cut-Norm 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:
  • Moser, Tardos, A Constructive Proof of the General Lovasz Local Lemma, JACM 2010.
  • Harvey and Vondrak, An algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles, 2015.
  • Kolmogorov, Commutativity in the Algorithmic Lovasz Local Lemma, FOCS 2016.
• Batson, Spielman and Srivastava, Twice-Ramanujan 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 Kadison-Singer 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:
  • Arora, Rao, Vazirani, Expander Flows, Geometric Embeddings and Graph Partitioning, STOC 2004.
  • Rothvoss, Lecture Notes on the ARV Algorithm for Sparsest Cut, 2016.
• Iterative rounding:
  • Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, FOCS 1998.
  • Singh and Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007.
• Extended formulations:
  • Yannakakis, Expressing Combinatorial Optimization Problems by Linear Programs, JCSS 1991.
  • Rothvoss, The matching polytope has exponential extension complexity.