Aaron Potechin - Sum of Squares Lower Bounds for Average Case Problems
Abstract: The sum of squares hierarchy (SoS) is a model of computation which is broadly applicable, surprisingly powerful, and in some sense simple. Thus, understanding the power of the sum of squares hierarchy gives considerable insight into which problems can be solved in polynomial time. Over the past few years, my collaborators and I proved SoS lower bounds on several fundamental average case problems, namely planted clique, tensor PCA (principal component analysis), sparse PCA, the Sherrington-Kirkpatrick problem, independent set on sparse graphs, densest k-subgraph, and non-Gaussian component analysis.
In this talk, I will introduce the sum of squares hierarchy and describe what sum of squares lower bounds for average case problems mean. I will then describe several of the fundamental average case problems we analyzed, why these problems are important, and our SoS lower bounds for them. At the end of my talk, I will briefly describe my other research projects over the past few years.
Speakers
Aaron Potechin
Aaron Potechin is an Assistant Professor of Computer Science at the University of Chicago. He received his Ph.D. from MIT in 2015, a Master’s degree from the University of Cambridge in 2010 (Part III of the Math Tripos), and his undergraduate degree from Princeton in 2009. His main research is on the sum of squares hierarchy, especially sum of squares lower bounds on average case problems. His other research interests include discrete math and the approximability of constraint satisfaction problems. Previously, Aaron researched analyzing monotone space complexity using the switching network model. For this work, he won the FOCS 2010 Machtey award for best student paper.
Much of Aaron’s research has been supported by an NSF SMALL grant and an NSF graduate research fellowship. For more information, see https://potechin.org/aaronpotechin/.
