Date & Time:
September 24, 2024 2:00 pm – 3:00 pm
Location:
JCL 390
09/24/2024 02:00 PM 09/24/2024 03:00 PM America/Chicago Aaron Potechin – Sum of Squares Lower Bounds for Average Case Problems JCL 390

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

Assistant Professor of Computer Science

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/.

Related News & Events

Pedro giving speech
UChicago CS News

Pedro Lopes Honored with 2025 IEEE VGTC Virtual Reality Significant New Researcher Award

Mar 13, 2025
ai generated network traffic
UChicago CS News

University of Chicago Researchers Revolutionize Network Traffic Generation with AI Breakthrough

Mar 12, 2025
UChicago CS News

Federal budget cuts threaten to decimate America’s AI superiority—and other countries are watching

Feb 25, 2025
Netflix logo on phone screen
UChicago CS News

The Hidden Cost of Netflix’s Autoplay: A Study on Viewing Patterns and User Control

Feb 25, 2025
Raul Castro Fernandez
UChicago CS News

Raul Castro Fernandez among six UChicago scientists awarded prestigious Sloan Fellowships in 2025

Feb 18, 2025
UChicago CS News

Quantum Leap: New Research Reveals Secrets of Random Quantum Circuits

Feb 04, 2025
UChicago CS News

Fred Chong from the Department of Computer Science Named ACM Fellow for Contributions to Quantum Computing

Jan 22, 2025
UChicago CS News

Rethinking AI as a Thought Partner: Perspectives on Writing, Programming, and More

Jan 16, 2025
UChicago CS News

UChicago Partners On New National Science Foundation Large-Scale Research Infrastructure For Education

Dec 10, 2024
UChicago CS News

Saturdays with CSIL — How Undergraduates are Transforming CS Education for Local High School Students

Dec 05, 2024
UChicago CS News

UChicago Researchers Receive Google Privacy Faculty Award for Research on AI Privacy Risks

Nov 22, 2024
UChicago CS News

The Climate App Designed to Tackle Chatham’s Flooding Crisis

Nov 21, 2024
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube