See below for an announcement about a talk and seminar series on the use
of semidefinite programming hierarchies in theoretical computer
science. This has overlap with quantum information via its connection
to separability-testing and the monogamy of entanglement.
aram
-------- Original Message --------
Subject: [Theory-reading-group] Talk + seminar on Sum of Squares
Date: Fri, 22 Aug 2014 11:11:36 -0400
From: Boaz Barak <b(a)boazbarak.org>
To: theory-reading-group(a)lists.csail.mit.edu
<theory-reading-group(a)lists.csail.mit.edu>
Hi,Â
For people on this list interested in Sum-of-Squares, Unique Games
Conjecture, etc.. I will give a general-audience talk on the Sum of
Squares method and its Theoretical Computer Science applications on
Wednesday September 3rd 10-11:30am, as well as an 11-week seminar series
on the topic on Mondays 2-5pm starting Sep 29th. (The talk and seminar
series will be independent of one another, and neither one is required
for following the other.) See titles and abstracts below, as well as the
webpage Â
http://www.boazbarak.org/sos for more information.
----
TALK TITLE: Sum of Squares Proofs and the Quest towards Optimal Algorithms
TIME AND PLACE: Wednesday, Sep 3rd, 10:00am-11:30am, room 32-G449 Kiva
ABSTRACT:
I will survey recent results and questions regarding the Sum-of-Squares
(SOS) method for solving polynomial equations. This method, which is
related to classical mathematical questions revolving around Hilbert's
17th problem, 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 verification, 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 be accessible for a general mathematically-mature
audience, and 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. If your interest is piqued by the talk, I will also
give a 11 week seminar series on this topic on Mondays 2pm-5pm starting
September 29th.
-----
SEMINAR SERIES TITLE: Sum of squares upper bounds, lower bounds, and
open problems.
TIME AND PLACE: Mondays 2-5pm, starting Sep 29, 32-G575
WEBPAGE:
http://www.boazbarak.org/sos
This mini-course/seminar series will cover recent results and research
directions on the "Sum of Squares" (SOS) algorithm, and its applications
to theoretical computer science.
The "Sum of Squares" algorithm was independently discovered by
researchers from several communities, including Shor, Nesterov, Parrilo,
and Lasserre, and is an algorithmic extension of classical math results
revolving around Hilbert's 17th question. It was recently proposed as a
route to resolving central theoretical CS questions  such as the truth
of Khot's "Unique Games Conjecture".
In these lectures I will cover the SOS algorithm from a theoretical
Computer Science perspective, with an emphasis onÂ
very recent results (including some not yet published..) showing its
power and limitations, as well as on the many open questions in this area.
Despite describing state of the art research, this course should be
accessible to first year graduate students or advanced undergraduate
students, as it requires no background except for "mathematical
maturity" and comfort with basic linear algebra and probability theory.
I will assume students are familiar with concepts such as eigenvalues
and eigenvectors,  norms and  basic inequalities such as
Cauchy-Schwarz/Holder, Â and probabilistic notions such as
expectation/variance, tail bounds such as Chernoff, and the
probabilistic method.Â
If you are interested in the course, please sign up for its mailing
list, which can be found from the course webpage
http://www.boazbarak.org/sos.
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip