Theory Lunch Seminar

Wednesday, December 8, 2021 - 12:00pm to 1:00pm

Location:

In Person and Virtual ET Gates Hillman 8102 and Zoom

Speaker:

JEFF XU, Ph.D. Student https://www.andrew.cmu.edu/user/sichaoxu/

Sum of Squares Lower Bounds for Sparse Independent Set

The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems. In the average case setting, SoS lower bounds provide strong evidence of algorithmic hardness or information-computation gaps. Prior to this work, SoS lower bounds have been obtained for problems in the “dense” input regime, while the sparse regime has remained out of reach. We make the first progress in this direction by obtaining strong SoS lower bounds for the problem of Independent Set on sparse random graphs. We prove that with high probability over an Erdõs–Rényi random graph G ~ G_{n,d/n} with average degree d > (log n)^2, degree-D SoS fails to refute the existence of an independent set of size k = Omega(\frac{n}{\sqrt{d}(log n)(D)^{c_0}})  in G (where c_0 is an absolute constant), whereas the true size of the largest independent set in G is O(\frac{n log d}{d}).

Joint work with Chris Jones, Aaron Potechin, Goutham Rajendran and Madhur Tulsiani.

Reference

In Person and Zoom Participation. See announcement.

Event Website:

https://www.cs.cmu.edu/~./theorylunch/

For More Information, Contact:

Keywords:

Seminar Series