<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div class=""><span class="" style="font-size: 14px;"><b class="" style="font-family: LucidaGrande; background-color: rgba(255, 255, 255, 0);"><u class="">Department of Computer Science </u></b><b class="" style="background-color: rgba(255, 255, 255, 0); font-family: LucidaGrande;"><u class="">Seminar</u></b></span></div></div><div class="" style="font-family: LucidaGrande;"><span class="" style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Monday, February 27, 2017</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">2:30 pm</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Ryerson 251 </span></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Aaron Potechin</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">(Institute for Advanced Study)</span></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class=""><span class="" style="font-size: 14px;"><span class="" style="font-family: LucidaGrande;">Title: Sum of Squares Lower Bounds for Planted Problems</span><br class="gmail-m_4827095062818533991gmail_msg"><br class="gmail-m_4827095062818533991gmail_msg"><span class="" style="font-family: LucidaGrande;">Abstract: </span></span></div><div class=""><font face="LucidaGrande" class=""><span class=""><span class=""><span style="font-size: 14px;" class="">The sum of squares hierarchy (SoS for short), a method for deciding the feasibility of a system of polynomial equations over the reals, is an exciting frontier of complexity theory, proof complexity, and real algebraic geometry. SoS is exciting because it can be applied to a wide variety of combinatorial optimization problems and is in fact conjectured to be optimal for many important problems. In particular, the sum of squares hierarchy captures the Goemans-Williamson algorithm for MAX-CUT, the Goemans-Linial algorithm for sparsest cut (analyzed by Arora-Rao-Vazirani), and the Arora-Barak-Steurer sub-exponential time algorithm for unique games. A recent sequence of results shows the power of SoS for a variety of machine learning problems, including dictionary learning and tensor decomposition and completion. Understanding the power and limitations of the sum of squares hierarchy is a major research program.</span></span></span></font></div><div class=""><font face="LucidaGrande" class=""><span class=""><span class=""><span style="font-size: 14px;" class=""><br class="">In this talk, I will describe the sum of squares hierarchy and my work on proving SoS lower bounds for planted problems, a broad class of problems where we are trying to distinguish between a random input and an input where a solution has been planted. Important planted problems include planted clique, tensor PCA (principal component analysis), and sparse PCA.<br class=""> </span><br class=""><br class=""><span style="font-size: 14px;" class="">-----</span><br class=""></span><span class="" style="font-size: 14px;"> </span><span class="" style="font-size: 14px;"><br class=""></span></span></font><span class="" style="font-size: 14px;"><span class="" style="font-family: 'Lucida Grande';">Bio: </span></span><font face="Lucida Grande" class=""><span style="font-size: 14px;" class="">Aaron Potechin is a researcher in computational complexity theory. He got his undergraduate degree in mathematics from Princeton, followed by Part III of the Math Tripos at Cambridge and a Ph.D in mathematics at MIT under Jonathan Kelner. He is currently finishing a joint two-year postdoc between Cornell and the Institute for Advanced Study with David Steurer and Avi Wigderson. </span></font><span style="font-size: 14px; font-family: 'Lucida Grande';" class="">Aaron dreams of proving substantial general circuit lower bounds someday. Thus far, his most important contributions have been proving monotone space lower</span><span style="font-size: 14px; font-family: 'Lucida Grande';" class=""> bounds with the switching network model and proving sum of squares lower bounds for planted problems.</span></div><div class=""><div class=""><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Host: Ketan Mulmuley</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class="" style="font-family: LucidaGrande;"><font size="2" class="">Refreshments in Ry. 255 after the talk</font></div></div></div></body></html>