Mondays, 3:00pm (sharp), Theory Lounge, or Wednesdays, 4:00pm (sharp), Theory Lounge.
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.