[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR

Tuesday, November 18, 2014
Ryerson 251 at 3:00 p.m.
 
Aaron Potechin
MIT
Web.mit.edu/techiya/www/members/apotech.html
 
Title: “Sum of Squares Lower Bounds for the Planted Clique Problem”
 
Abstract: The planted clique problem asks whether or not we can find a k-clique which is planted in a random G(n,1/2) graph. Although the expected size of the largest clique in a random graph is only 2lg(n), we currently do not know of any polynomial time algorithm which can find a planted clique of size much smaller than n^(1/2).
The sum of squares hierarchy gives a hierarchy of approximation algorithms, each more powerful than the last. These algorithms are some of the most powerful approximation algorithms we know of and their performance on many problems is not well understood. In fact, until very recently there were no non-trivial bounds on the performance of the sum of squares hierarchy on the planted clique problem.
In this talk, I will present the first non-trivial bounds for this question, describing the planted clique problem, the sum of squares hierarchy, and how we can show that the sum of squares hierarchy fails to find the planted clique if its size k is sufficiently small.
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served in Ryerson 255 at 2:30pm*
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141114/2571de18/attachment.htm