About this series

The Quarterly Theory Workshop brings in three theoretical computer science experts present their perspective and research on a common theme.  Chicago area researchers with interest in theoretical computer science are invited to attend.  The technical program is in the morning and includes coffee and lunch.  The afternoon of the workshop will allow for continued discussion between attendees and the speakers.

Synopsis

This Quarterly Theory Workshop is on the theme of semidefinite programming hierarchies and specifically, the sum of squares hierarchy.  This theme will explore the recent progress in fundamental questions in algorithms and complexity using semidefinite programming hierarchies. In particular, the “sum of squares” hierarchy provides a new family of algorithms, whose power and limitations have not yet been understood to satisfaction, and provides for exciting avenues of research. The speakers are Boaz Barak, Prasad Raghavendra, David Steurer and Madhur Tulsiani. The talks will be video recorded.
  • Date: Monday, May 16 and Tuesday, May 17, 2016.
  • Location:
    • Tuesday: ITW Lecture Hall (1st floor), Ford Motor Company Engineering Design Center (map), Northwestern U, 2133 Sheridan Rd, Evanston, IL 60208.
    • Monday:Technological Institute, Room L324 , 2145 Sheridan Road
      Evanston, IL 60208 map it
  • Transit: Noyes St. Purple Line (map).
  • Parking: Validation for North Campus Parking Garage (map) available at workshop.
  • Registration: none necessary, bring your own name badge from past conference.

Schedule

Monday May 16th.
10:30am: Madhur Tulsiani: An Introduction to Sum-of-Squares and SDP hierarchies.

This talk will be held in Tech L324 (different from the location on Tuesday).

Tuesday May 17th. 

9:00 am – 9:30am: Breakfast
9:30 am – 10:15am: David Steurer: Tensor decompositions, sum-of-squares proofs, and spectral algorithms. (video)
10:20 – 10:30am: Coffee Break
10:30am – 11:15am: Prasad Raghavendra: Lower Bounds on the Size of Semidefinite Programming Relaxations. (video)
11:20am – 11:30am: Coffee Break
11:30 am – 12:15 pm: Boaz Barak: Do algorithms believe in unicorns? (video)

Abstracts

Title: An Introduction to Sum-of-Squares and SDP hierarchies
Speaker: Madhur Tulsiani

Abstract: This talk will provide an introduction to different views of the sum-of-squares hierarchy, as relaxations of integer programs, and as proof systems. We will discuss different ways of reasoning using the relaxations given by the hierarchy, and give a brief overview of some of the known algorithmic and hardness results.

No prior knowledge of SDP hierarchies or proof systems will be assumed for the talk.

 

Title: Tensor decompositions, sum-of-squares proofs, and spectral algorithms.

Speaker: David Steurer (Cornell University)
Video link. 

Abstract: The problem of finding low-rank decompositions of tensors has a wide-range applications, e.g., for learning various mixture models. In the overcomplete regime—when the rank is superlinear in the dimension—most known provable decomposition methods for third-order tensors break down.

We describe a polynomial-time algorithm based on the sum-of-squares method that is able to approximately decompose random n-dimensional third-order tensors of rank up to n^{3/2}/polylog n. The previous best algorithm by Ge and Ma also used sum-of-squares but required quasi-polynomial time to achieve such decompositions.

Finally, we demonstrate how to reap the benefits of the sum-of-squares method without solving large semidefinite programs: Using the sum-of-squares toolkit, we devise new kinds of spectral algorithms that achieve similar decomposition guarantees as sum-of-squares but with running times that are close to linear in the size of the input (exponent 1.125 using fast matrix-multiplication).

Based on joint works with Sam Hopkins, Tengyu Ma, Tselil Schramm, and Jonathan Shi. 

 

Title: Lower Bounds on the Size of Semidefinite Programming Relaxations

Speaker: Prasad Raghavendra (UC Berkeley)
Video link.

Abstract: We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2^{n^c}, for some constant c>0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.
This is joint work with James Lee (U. Washington) & David Steurer (Cornell Univ).

 

Title: Do algorithms believe in unicorns?

Speaker: Boaz Barak (Harvard University)
Video link. 

Abstract: Bayesian analysis uses probabilities to model uncertainty. Traditionally this uncertainty is due to a lack of *information* but, in many cases uncertainty of observers is  due to a lack of *computational resources*.  That is, in an information theoretic sense the observations completely determine the unseen parameters, but recovering the parameters from the observed data is a hard computational problem.

In this talk I will discuss one way to assign internally consistent Bayesian probabilities to model computational uncertainty, based on the Sum of Squares (SoS) semidefinite programming hierarchy (Shor ’87, Parrilo ’00, Lasserre ’01). I will illustrate this notion via the example of the *planted clique problem* (Karp ’76, Jerrum ’92, Kucera ’95).
This is a central problem in average case complexity that has been connected to questions in a variety of areas including cryptography, computational economics, computational biology, sparse recovery, and machine learning.
We show that for every constant epsilon, the SoS algorithm requires  n^{Omega(log n)} time to detect a planted clique of size n^{1/2-epsilon} in a G(n,1/2) Erdos-Renyi random graph. We do so by giving a general approach to find consistent probabilities to model the uncertainty of the SoS algorithm on the location of the planted clique. Interestingly, a computationally restricted agent must make probabilistic inferences about objects that do not exist (such as a large clique in a random graph), hence a theory of computational Bayesian probabilities needs to make sense of quantities such as “the probability that a unicorn has blue eyes”.
I will not assume background in semidefinite programming and the talk will aim to be accessible (and hopefully enjoyable)  to anyone interested in uncertainty, data analysis, and algorithms
Based on joint work with Hopkins, Kelner, Kothari, Moitra and  Potechin.