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:
- 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 ;
- in the dense-regime, obtain a sharper bound for the ellipsoid fitting conjecture that is tight up-to an absolute constant;
- 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/