[Colloquium] CS Seminar today at 2:30 pm: Aaron Potechin, IAS

[Sandra Wallace via Colloquium]

Department of Computer Science Seminar

Monday, February 27, 2017
2:30 pm
Ryerson 251 

Aaron Potechin
(Institute for Advanced Study)

Title: Sum of Squares Lower Bounds for Planted Problems

Abstract: 
The sum of squares hierarchy (SoS for short), a method for deciding the feasibility of a system of polynomial equations over the reals, is an exciting frontier of complexity theory, proof complexity, and real algebraic geometry. SoS is exciting because it can be applied to a wide variety of combinatorial optimization problems and is in fact conjectured to be optimal for many important problems. In particular, the sum of squares hierarchy captures the Goemans-Williamson algorithm for MAX-CUT, the Goemans-Linial algorithm for sparsest cut (analyzed by Arora-Rao-Vazirani), and the Arora-Barak-Steurer sub-exponential time algorithm for unique games. A recent sequence of results shows the power of SoS for a variety of machine learning problems, including dictionary learning and tensor decomposition and completion. Understanding the power and limitations of the sum of squares hierarchy is a major research program.

In this talk, I will describe the sum of squares hierarchy and my work on proving SoS lower bounds for planted problems, a broad class of problems where we are trying to distinguish between a random input and an input where a solution has been planted. Important planted problems include planted clique, tensor PCA (principal component analysis), and sparse PCA.
     

-----
 
Bio:  Aaron Potechin is a researcher in computational complexity theory. He got his undergraduate degree in mathematics from Princeton, followed by Part III of the Math Tripos at Cambridge and a Ph.D in mathematics at MIT under Jonathan Kelner. He is currently finishing a joint two-year postdoc between Cornell and the Institute for Advanced Study with David Steurer and Avi Wigderson.  Aaron dreams of proving substantial general circuit lower bounds someday. Thus far, his most important contributions have been proving monotone space lower bounds with the switching network model and proving sum of squares lower bounds for planted problems.


Host: Ketan Mulmuley

Refreshments in Ry. 255 after the talk
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170227/55051215/attachment.html>