Speaker: Dr. Boaz Barak(Microsoft Research)
Time & date: 4:00pm - 5:30pm, Aug 6th
Place: CELC seminar room (404, 4F)
TITLE: Sum of Squares Proofs and the Quest towards Optimal Algorithms

ABSTRACT:
I will survey recent results and questions regarding the Sum-of-quares (SOS) method for 
solving polynomial equations. This method, which is related to classical mathematical questions, 
has been studied in several scientific disciplines, including real algebraic geometry, 
proof complexity, control theory, and mathematical programming, and has found applications 
in fields as diverse as quantum information theory, formal erification, game theory and many others. 
We discuss some new perspectives on the SOS method, giving different interpretations 
and applications of it, and raising the question whether it could yield a generic *optimal* algorithm 
for broad domains of computational problems. 
We will also discuss the fascinating relation between the SOS method and 
Khot's Unique Games Conjecture, which is a tantalizing conjecture in computational complexity 
that has the potential to shed light on the complexity of a great many problems. 
The talk will assume no background on the SOS method or the unique games conjecture. 
It is partially based on joint works with Jonathan Kelner and David Steurer.