[Colloquium] 9/24 Aaron Potechin (UChicago) Sum of Squares Lower Bounds for Average Case Problems

[Holly Santos via Colloquium]

Department of Computer Science Colloquium

Aaron Potechin
University of Chicago
Assistant Professor of Computer Science

Tuesday, September 24th
2:00pm - 3:00pm
In Person: John Crerar Library Rm 390

Title: 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.

Bio: 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, se https://potechin.org/aaronpotechin/.

[Image 2.jpeg]

---
Holly Santos
Executive Assistant to Hank Hoffmann, Chairman
Department of Computer Science
The University of Chicago
5730 S Ellis Ave-217   Chicago, IL 60637
P: 773-834-8977
hsantos at uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240903/72c8651f/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Image 2.jpeg
Type: image/jpeg
Size: 12886 bytes
Desc: Image 2.jpeg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240903/72c8651f/attachment-0001.jpeg>