Proofs for
Algorithms, Algorithms from Proofs
The
interplay between *algorithms* and *proofs* has been one of the most
fascinating and fruitful themes in theoretical
Computer
Science. In this talk I will describe a different connection between these two
concepts - a general methodology for algorithm design using an automatic
transformation of a proof into an algorithm. This methodology yields a
systematic way to design and analyze algorithms across many domains. In
particular we and others have used it for problems in combinatorial
optimization, machine learning, and quantum information theory, and it shows
promise for making progress on important open questions such as settling Khot's
Unique Games Conjecture. I will demonstrate this methodology by presenting an
algorithm for the Sparse Coding / Dictionary Learning problem that handles much
more general inputs than was known before, and an algorithm for the Unique
Games problem that can solve all the previously known candidate hard instances.
Key
to our approach is the notion of "pseudo-distributions", which are
objects that are emphatically different than actual distributions but behave
like them in the eyes of low degree polynomials. We use these
pseudo-distributions to "lift" a proof into an algorithm via the
Shor-Parrilo-Lasserre "Sum-of-Squares" semidefinite programming
hierarchy. The talk will be based on several joint works with (varying subsets
of) Fernando Brandao, Aram Harrow, Jonathan Kelner, David Steurer and Yuan
Zhou.
BIO:
Boaz
Barak received his Bachelor's degree from Tel Aviv University in 1999 and his
Ph.D from the Weizmann Institute of Science in 2004.
Following
a postdoc at the Institute for Advanced Study, Boaz joined the faculty of
Princeton University where he was most recently an associate professor of
Computer Science. In 2010 he joined Microsoft Research New England where he is
now a senior researcher.
Boaz
is interested in all aspects of theoretical computer science, and in particular
cryptography, computational complexity, and algorithms. He has won the ACM
doctoral dissertation award in 2004, a Packard fellowship in 2007, and was
recently selected by Foreign Policy magazine for its list of 100 leading global
thinkers for 2014.
- Tags
-