[Colloquium] TODAY 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

Zoom:
https://uchicagogroup.zoom.us/j/98533385952?pwd=aAmyuJN8YC2Al9P28PZ0DWIJnCX6wB.1

Meeting ID: 985 3338 5952
Passcode: 335879

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, see https://potechin.org/aaronpotechin/ <https://urldefense.com/v3/__https://potechin.org/aaronpotechin/__;!!BpyFHLRN4TMTrA!_O4R48q232Ig26c6RSDXm8SWrtmyFmKMYsSLNptwIit45lh_kPCTRu47DCk4dnaLcmksFRWUR27TsbdtkaWSuCLAXUCCyoeuZHM$>.



---
Holly Santos
Executive Assistant to Hank Hoffmann, Liew Family Chair
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/20240924/e8101f06/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Image 2.jpeg
Type: image/jpeg
Size: 12886 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240924/e8101f06/attachment-0001.jpeg>