<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body style="overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<i>Department of Computer Science Colloquium</i></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<i><br>
</i></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>Aaron Potechin</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>University of Chicago</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>Assistant Professor of Computer Science</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b><br>
</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>Tuesday, September 24th </b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>2:00pm - 3:00pm </b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>In Person: John Crerar Library Rm 390</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b><br>
</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>Title: Sum of Squares Lower Bounds for Average Case Problems</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b><br>
</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>Abstract: </b>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.</div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<br>
</div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
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.</div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b><br>
</b></div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<b>Bio: </b>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.</div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
<br>
</div>
<div style="caret-color: rgb(60, 64, 67); color: rgb(60, 64, 67); font-family: Roboto, Helvetica, Arial, sans-serif;">
Much of Aaron's research has been supported by an NSF SMALL grant and an NSF graduate research fellowship. For more information, se <a href="https://potechin.org/aaronpotechin/" target="_blank" style="color: rgb(26, 115, 232);">https://potechin.org/aaronpotechin/</a>.</div>
<div><br>
</div>
<img alt="Image 2.jpeg" src="cid:817EBED0-7208-4EEE-A6B7-1B3DA86B7004">
<div><br>
</div>
<div>---<br class="Apple-interchange-newline">
<div>
<div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<div>Holly Santos<br>
Executive Assistant to Hank Hoffmann, Chairman<br>
Department of Computer Science<br>
The University of Chicago<br>
5730 S Ellis Ave-217 Chicago, IL 60637<br>
P: 773-834-8977<br>
hsantos@uchicago.edu<br>
</div>
</div>
</div>
<br>
</div>
</body>
</html>