Swedish Summer School in Computer Science – S^{3}CS 2014 

About the CoursesBoaz Barak: Sums of SquaresI am going to give a tutorial on the "Sum of Squares" (also known as "Lasserre") semidefinite programming hierarchy from a theoretical computer science perspective. This is a natural algorithm for solving polynomial equations that has been proposed by researchers from different communities, and has recently been the object of much interest in TCS because it is a natural candidate algorithm to tackle some longstanding open questions. I will give an introduction to this algorithm and its connection to classical questions in mathematics on certifying that a function is nonnegative by writing it as a sum of squares. I will then present some of the applications of this algorithm, as well as known lower bounds, and how both can be analyzed using the above connection. There is much we don't know about this algorithm, and so I will also discuss some of the many open problems and research directions in this area. The course will be accessible to beginning graduate students in TCS and will not assume prior knowledge in convex optimization or algebraic geometry (at least I hope so, because I don't have any...). Ryan O'Donnell: Analysis of Boolean FunctionsBoolean functions, f : {0,1}^n > {0,1}, are perhaps the most basic object of study in computer science. In this workshop we will investigate them via their Fourier transform and other analytic methods. Besides developing basic techniques, we will see the emergence of a number of themes:
Finally, we will see the tools and themes of Analysis of Boolean Functions applied to problems in learning theory, communication complexity, property testing, NPhardness of approximation, and random graph theory. 
