[Colloquium] REMINDER: 1/26 Talks at TTIC: Tselil Schramm, UC Berkeley

[Mary Marre via Colloquium]

When:     Thursday, January 26th at 11:00 am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Tselil Schramm, UC Berkeley


Title:        Adventures with Sum-of-Squares

Abstract: The sum-of-squares hierarchy is a family of semidefinite programs
that can capture any combinatorial optimization problem, allowing one to
trade runtime for accuracy. The class of problems that sum-of-squares can
solve efficiently is still not well-characterized---recently this has been
a topic of intensive study in the theoretical computer science community,
as the hierarchy has the potential to resolve long-standing open problems
in the theory of approximation algorithms. In this talk, I will describe my
own efforts towards characterizing the sum-of-squares hierarchy, through
the lens of average-case problems. I'll talk about sum-of-squares
algorithms for refuting random constraint satisfaction problems, about
sum-of-squares lower bounds for planted clique and other average-case
problems, and about using sum-of-squares algorithms to obtain fast spectral
algorithms.


Host: Yury Makarychev <yury at ttic.edu>



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170125/cc93a3f5/attachment.html>