Pseudocalibration and SoS Lower Bounds
summary
A mechanical construction called pseudo-calibration projects the relative-density function of a planted distribution to a low-degree projection in the graph variables and sets entries M_ST(G)=sum_{|α|≤D} λ̂_ST(α) χ_α(G). This yields a candidate moment matrix whose PSDness one proves by a symbolic Cholesky-style factorization. Result: degree-d Sum-of-Squares fails to refute a planted clique of size about Θ(√(d / log n)) (so d≈log n suffices to break the gap); method also recovers tight SoS lower bounds for planted CSPs like random 3-XOR.
AI-written summary · about