<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Hi everyone,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">As a heads up, this quarter I am teaching my course on the sum of squares hierarchy, which is my research specialty. While there is some linear and semidefinite programming
involved, the material is primarily theoretical and the only prerequisite is linear algebra. The course description is below.<br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">Best,<br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">Aaron<br>
</span>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">
Course Title: Topics in Theoretical Computer Science: The Sum of Squares Hierarchy<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">
Course Times: MW 4:30-5:50 in Ryerson 251<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)">
<p><span>Course Description:</span></p>
<p>The sum of squares hierarchy (SoS) is a hierarchy of semidefinite programs which is broadly applicable, surprisingly powerful, and in some sense, simple. In particular, SoS can be applied to almost any combinatorial optimization problem and captures the
best known algorithms for several of these problems including max cut, sparsest cut, and unique games. However, at its heart, all SoS is using is polynomial equalities and the fact that squares are non-negative over the real numbers.</p>
<p> </p>
<p>The goal of this course is to give a good intuition for SoS by describing much of what is known so far about SoS. Topics which will be covered include semidefinite programming, Positivstellensatz/SoS proofs, pseudo-expectation values, the Goemans-Williamson
algorithm for max cut, linear and semidefinite programs for sparsest cut, applications of SoS to planted sparse vector and tensor completion, SoS lower bounds for 3-XOR, knapsack, and planted clique, the unique games conjecture, and the small-set expansion
hypothesis.</p>
</div>
<br>
</div>
</body>
</html>