Computer Science Speaking Skills Talk / Theory Lunch Seminar

— 1:00pm

Location:
In Person - Gates Hillman 8102

Speaker:
JEFF XU , Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.andrew.cmu.edu/user/sichaoxu/

Walk Global, Think Local: towards Sharp Sum-of-Squares Lower Bounds

Sum-of-Squares lower bounds are arguably the strongest evidence we have for algorithmic intractability in the average-case setting.  Despite the steady flow of progress in the dense regime, our understanding remains rather limited in the sparse regime, even for just degree-4 SoS. Among various obstacles, a major difficulty is to understand the spectral behaviors of a large class of random matrices with correlated entries. In fact, non-trivial challenges posed by sparsity are already present in the adjacency matrix of random graphs with a bounded average degree.

In this talk, I will describe how we overcome this technical challenge by proposing a "local" reinterpretation of trace-method. As a result, the substantially refined understanding allows us to:

  1. in the ultra-sparse regime, obtain the first higher-degree Sum-of-Squares lower bounds in G_{n,d/n} for d=O(1) for independent set and coloring ;
  2. in the dense-regime, obtain a sharper bound for the ellipsoid fitting conjecture that is tight up-to an absolute constant;
  3. in the intermediate regime, obtain tight hardness for the Densest-k-Subgraph problem matching log-density framework.

Presented as part of the Theory Lunch Seminar

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

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

Add event to Google
Add event to iCal