[Colloquium] 12/14 Young Researcher Seminar Series: Samuel Hopkins, Cornell

[Mary Marre via Colloquium]

When:     Wednesday, December 14th at 11:00 am

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

Who:       Samuel Hopkins, Cornell

Title:        A Nearly-Tight Sum-of-Squares Lower Bound for the Planted
Clique Problem

Abstract:
The Sum-of-Squares meta-algorithm has emerged as a powerful and unifying
algorithm design technique for problems in numerous settings.
In particular, much recent work has applied the Sum-of-Squares approach to
obtain improved algorithms for average-case or planted problems.
Some of these problems are members of the classic complexity theory zoo
(e.g. random CSPs), while some are inspired by recent machine learning
literature (e.g. random tensor decomposition).
In this talk, we investigate the tantalizing possibility of using
Sum-of-Squares to design an improved algorithm for the Planted Clique
problem---the problem of recovering a large clique hidden in a random graph
G(n,1/2).
This problem, immune to every algorithmic attack made on it for 20 years,
has become a key assumption in proving computational hardness of many
statistical or average-case problems.

Ultimately, we show that Sum-of-Squares cannot give substantially improved
algorithms for planted clique.
Along the way, however, we will encounter strong evidence that
Sum-of-Squares is a strictly stronger algorithm design technique for
average-case problems than other powerful algorithmic frameworks, such as
linear programming and spectral methods.
We will emphasize a new technique, called pseudocalibration, to analyze
Sum-of-Squares algorithms, which we believe will have broad applications to
convex programming algorithms for statistical problems.

Based on joint work with Boaz Barak, Jon Kelner, Pravesh Kothari, Ankur
Moitra, and Aaron Potechin


Host: *Madhur Tulsiani <madhurt at ttic.edu>*

************************************************************
**************************************



The TTIC Young Researcher Seminar Series (http://www.ttic.edu/young-
researcher.php) features talks by Ph.D. students and postdocs whose research is
of broad interest to the computer science community. The series provides an
opportunity for early-career researchers to present recent work to and meet
with students and faculty at TTIC and nearby universities.


The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.

For additional information, please contact Matthew Walter (mwalter 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/20161208/3b4c80a2/attachment.html>