Mondays, 3:00pm (sharp), Theory Lounge, or Wednesdays, 4:00pm (sharp), Theory Lounge.

- March 4 (Wed 4pm),
**Lap Chi**on Approximating independent set in sparse graphs - March 11 (Wed 4pm),
**Sam**on Approximating ATSP by Relaxing Connectivity - March 16 (Mon 3pm),
**Aaron**on Fast Generation of Random Spanning Trees and the Effective Resistance Metric - April 8 (Wed 4pm),
**Prasad**on Lasserre SDP Lower bounds for planted clique - April 22 (Wed 4pm),
**Jingcheng**on Connectivity in Random Forests and Credit Networks - April 27 (Mon 3pm),
**Nima**on Randomized Rounding for the Largest Simplex Problem - May 4 (Mon 3pm),
**Fotis**on On Finding Perfect Objects - The Lovasz Local Lemma and beyond - May 11 (Mon 3pm),
**Ali**

**March 4 (Wed 4pm), Approximating independent set in sparse graphs**

This paper by Nikhil Bansal shows that the maximum independent set problem on graphs with maximum degree d can be approximated within a factor of O~(d / log^2 d) using a mixed SDP/LP hierarchy, almost matching the unique games hardness result of the problem. The proof is nonconstructive and uses a Ramsey-type result proved by Alon. Time permitting, we will also discuss the subsequent work "On the Lovasz Theta function for independent sets" by Bansal, Gupta and Guruganesh, who gave almost matching algorithmic proofs along with some other related results.

**March 11 (Wed 4pm), Approximating ATSP by Relaxing Connectivity**

Constant approximation algorithms for the asymmetric traveling salesman problem (ATSP) have proved elusive despite many attempts over the past three decades. In an exciting recent work, Ola Svensson obtained a constant approximation algorithm for a rather general special case of ATSP. Similar to the recent development for TSP, he assumes that the metric is given by some underlying graph. His key idea is to modify the old idea of cycle cover, and instead try to obtain global connectivity from local connectivity. I will give an overview of his algorithm, and if time permits, discuss the difficulty in extending the approach to the general case.

**March 16 (Mon 3pm), Fast Generation of Random Spanning Trees and the
Effective Resistance Metric**

Two papers, one by Kelner and Madry and the other by Madry, Straszak, and Tarnawski, have introduced exciting new ways of using random walks to compute uniformly random spanning trees. Both of these algorithms improve on the method that simulates a random walk in full, which takes O(mn) time in the worst case. In this talk, I will briefly summarize the algorithm from the first paper, which obtains a O(m\sqrt{n}) time algorithm using ball-growing partitioning methods and Laplacian solvers to shortcut the random walk. I will then discuss the second paper's improvements, which partition the graph using the effective resistance metric.

**April 8 (Wed 4pm), Lasserre SDP Lower bounds for planted clique**

In this talk, I will survey recent results by Meka-Potechin-Wigderson (http://http://arxiv.org/abs/1503.06447) and Deshpande-Montanari (http://arxiv.org/abs/1502.06590) showing Lasserre SDP lower bounds for planted clique.

**April 22 (Wed 4pm), Connectivity in Random Forests and Credit Networks**

In this talk, I will sketch the proofs of several properties about random forests by Goel, Khanna, Raghvendra, Zhang. In particular, it provides evidence for the negative correlation conjecture about forests, a long-standing open problem. Time permitted, I'll also discuss the current status of the negative correlation conjecture, and its algorithmic implication to random walks.

**April 27 (Mon 3pm), Randomized Rounding for the Largest Simplex
Problem**

In this talk I will introduce the problem of finding the maximum volume j-dimensional simplex contained inside the convex hull of n given points and its connections to the \ell_2 hereditary discrepancy. Then I will go over the recent result by Alexandar Nikolov who obtains the first exp(O(j))-approximation algorithm for it. If time permits I will also discuss a volume-based analogue of Bourgain-Tzafriri’s restricted invertibility principle which is proved in the same paper using very similar techniques.

**May 4 (Mon 3pm), On Finding Perfect Objects - The Lovasz Local Lemma
and beyond**

In this talk I will introduce the problem of finding perfect objects and explain its connection to the Lovasz Local Lemma. I will survey papers on the algorithmic aspects of the Local Lemma, from the original Moser-Tardos paper http://arxiv.org/pdf/0903.0544v3.pdf and its extensions to the most recent result of Harvey and Vondrak http://arxiv.org/pdf/1504.02044.pdf, as well as the framework of Achlioptas and I. http://arxiv.org/pdf/1406.0242.pdf.

Some papers suggested by the participants.

- Clustered Integer 3SUM via Additive Combinatorics, by Chan and Lewenstein.
- A Proof Of The Block Model Threshold Conjecture, by Mossel, Neeman, and Sly.
- On Monotonicity Testing and Boolean Isoperimetric type Theorems, by Khot, Minzer, and Safra.
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric, by Madry, Straszak, and Tarnawski.
- The Simplex Algorithm is NP-mighty, by Disser and Skutella.
- Sperner's Colorings, Hypergraph Labeling Problems and Fair Division, by Mirzakhani and Vondrak.
- Contagious Sets in Expanders, by Coja-Oghlan, Feige, Krivelevich, Reichman.
- Connectivity in Random Forests and Credit Networks, by Goel, Khanna, Raghvendra, Zhang.
- A Tight Linear Time 1/2-Approximation for Unconstrained Submodular Maximization, by Buchbinder, Feldman, Naor, and Schwartz.
- Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs, by Madry.