STOC 2014: 46th Annual Symposium on the Theory of Computing

Tutorials and workshops

Tutorials and workshops will be held on Saturday, May 31, 2014 at Columbia University.

There will be three full-day tutorials focusing on the following subjects:

  1. Recent Advances on the Lovasz Local Lemma
  2. Efficient Distribution Estimation
  3. Overcoming the intractability bottleneck in unsupervised machine learning

Location: The workshops are in Mudd Hall and Shapiro Center at Columbia University. The easiest way to reach this location is to take the 1 subway to 116 St., and enter campus though the main gate. Head to the north east corner of campus. A map can be found here

Lunch: You are on your own for lunch. There are many good and reasonably priced lunch options within walking distance. If you walk south on Broadway or north on Amsterdam, you will find many restaurants including Italian, Ethiopian, Thai, Indian, Mexican, Korean, Japanese, Chinese and even American. Here is a recent guide to some of the restaurants in the area.

Recent Advances on the Lovasz Local Lemma

Organizers: David Harris, Aravind Srinivasan, Mario Szegedy, Gabor Tardos

Synopsis: The Lovasz Local Lemma (LLL) is a fundamental probabilistic tool; there has been much recent progress related to it, especially on various algorithmic versions and generalizations. In this workshop, we will cover classical and modern material; the "classical" material includes powerful extensions like iterated applications of the LLL which are not that well known, and the modern material includes very recent information-theoretic insights into the LLL and its Moser/Moser-Tardos algorithmic versions. Various applications, connections to physics, and derandomization will be among the further aspects covered.

Location: 303 Mudd Hall


9:15-9:45 Coffee (outside 303 Mudd Hall)
9:45-10:35:Aravind Srinivasan: A crown jewel of the Probabilistic Method
  - The basic Lovasz Local Lemma (LLL)
- Proof
- Simple applications
- Iterated LLL (a surprisingly powerful version) and applications to routing and coloring
10:45-11:35 Mario Szegedy: What are the limits?
  - Shearer's precise formulas
- Connections to statistical physics
- A counter example to the Shearer's bound in the variable setting.
11:35-1:30 Lunch (on your own)
1:30-2:20 Bernhard Haeupler: Constructive aspects
  - Moser-Tardos, proof using recurrences
- The LLL distribution of Haeupler et al. and applications (e.g., to the Santa Claus problem)
- Derandomization
2:30-3:20 David Harris: Beyond the ordinary LLL
  - Lopsided LLL revisited, with applications
- Partial resampling
- Permutation LLL
3:20-3:45 Coffee (outside 303 Mudd Hall)
3:45-4:35 Dimitris Achlioptas: Algorithmic progress as compression
  - Moser's information-theoretic/compression argument.
- Very recent information-theoretic insights, a local progress lemma.

Efficient Distribution Estimation

Organizers: Ilias Diakonikolas, Gregory Valiant

Synopsis: The broad question of how to infer information or accurately estimate properties of a distribution based on random samples is of fundamental importance across the sciences. Additionally, questions in this vein have rich mathematical structure, requiring tools and intuitions from probability, combinatorics, analysis, and information theory. This question is also distinctly computational in nature; at the end of the day, the goal is to describe algorithms efficient from both a computational and information theoretic standpoint and understand the behavior of these algorithms. The recent flood of data, especially from the biological sciences, has provided fresh perspective on some of these problems, and offers the tantalizing possibility that new theoretical developments may very quickly find their way into meaningful practical applications.
The goal of this workshop is to introduce the broad CS theory community to central problems and techniques in this area of distributional property estimation, and discuss some new directions and opportunities for future work that lie between computation and statistics.

Location: 833 Mudd Hall


9:15-9:45 Coffee (outside 303 Mudd Hall)
9:45-10:35 Ronitt Rubinfeld (MIT and Tel Aviv University): Taming distributions over big domains
10:45-11:35 Rocco Servedio (Columbia): A complexity theoretic perspective on unsupervised learning
11:35-1:30 Lunch (on your own)
1:30-2:20 Gregory Valiant (Stanford): Distributional Property Testing and Estimation: Past, Present, and Future
2:30-3:20 Paul Valiant (Brown): Lower Bound Techniques for Statistical Estimation Tasks
3:20-3:45 Coffee (outside 303 Mudd Hall)
3:45-4:35 Ilias Diakonikolas (Edinburgh): Beyond Histograms: Exploiting Structure in Distribution Estimation
4:45-5:30 Costis Daskalakis (MIT): Beyond Berry Esseen: Structure and Learning of Sums of Random Variables

Overcoming the intractability bottleneck in unsupervised machine learning

Organizers: Sanjeev Arora, Rong Ge, Ankur Moitra

Synopsis: Unsupervised learning — i.e., learning with unlabeled data — is increasingly important given today's data deluge. Most natural problems in this domain — e.g., for models such as mixture models, HMMs, graphical models, topic models and sparse coding/dictionary learning — are NP-hard. Therefore researchers in practice use either heuristics or convex relaxations with no concrete approximation bounds. Several nonconvex heuristics work well in practice, which is also a mystery.
Recently, a sequence of results has shown that rigorous approaches leading to polynomial running time are possible for several of these problems. These involve sidestepping worst-case complexity via special assumptions on the input. Some of this work — e.g., for topic models — even leads to practical running times (50x faster than previous approaches). It has even become possible to analyse nonconvex optimization heuristics such as alternating minimization or kSVD.
This day of talks is meant to introduce the TCS audience to this area, the progress that has been made, and interesting open problems that remain. Yann Le Cun, Director of AI Research at Facebook Labs, will tell us about the surprising power of heuristics in practice.

Location: 417 Shapiro Center


9:15-9:45 Coffee (outside 303 Mudd Hall)
9:45-10:30 Sanjeev Arora (Princeton): Intractable problems in unsupervised learning: a new frontier for theoretical CS
10:45-11:30 Yann LeCun (NYU, Director of AI Research, Facebook Labs): Nonconvex optimization techniques in ML (including deep learning) and their surprising power
11:35-1:30 Lunch (on your own)
1:30-2:15 Michael Jordan (UC Berkeley): Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
2:30-3:15 Daniel Hsu (Columbia): Tensor-decomposition based approaches for model fitting
3:15-3:45 Coffee (outside 303 Mudd Hall)
3:45-4:30 Ankur Moitra (MIT): Provable algorithms for dictionary learning/sparse coding (and analysis of nonconvex heuristics)
4:45-5:30 Rong Ge (MSR New England): Provable algorithms for learning some deep nets