Theory Lunch Seminar - Jeff Xu

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

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

SoS Lower Bounds for Coloring Random Graphs

Coloring for random graph from G(n,1/2) is a classic example exhibiting an Information v. Computation gap: it has chromatic number of θ(n/log n) w.p. 1-o(1) while the best efficiently certifiable lower bound is θ(√{n}) achieved by basic SDP. Unlike the related question of independence number where we have essentially matching hardness and algorithms in various restricted models, our hardness evidence for coloring was surprisingly limited to the basic SDP. I will talk about lower bounds against Sum-of-Squares algorithms showing that the order root-n bound is essentially the best we can hope for in poly time. 

In the past few years, low-degree polynomial method has become a popular heuristic in predicting hardness for average-case problems, but it also may be fairly limited in various problem-specific applications: for example, coloring on dense random graph is a problem whose natural distinguishing variant is “easy”. Against the conventional wisdom that some form of low-degree hardness is a necessary precursor for SoS lower bounds, we circumvent the lack of low-degree hardness, and design our SoS lower bounds via a systematic departure from the “pseudo-calibration” recipe. 

This is based on a joint work with Aaron Potechin (UChicago).

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

Add event to Google
Add event to iCal