[Colloquium] Re: 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>*

On Wed, Jan 25, 2017 at 11:29 AM, Mary Marre <mmarre at ttic.edu> wrote:

> 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 <(773)%20834-1757>*
> *f: (773) 357-6970 <(773)%20357-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/20170126/abe07137/attachment-0001.html>