The constant-degree sum-of-squares barrier conjecture for random matrices

About 1 year old · traced to

Fix 1<α<21<\alpha<2, set T=NαT=N^\alpha, and let MranM_{ran} be a random T×NT\times N Gaussian matrix. Let v∈RNv\in\mathbb R^N satisfy ∥v∥∞≤1\|v\|_\infty\leq1, and suppose ∣(Mranv)j∣≥Nσ|(M_{ran}v)_j|\geq N^\sigma for every j∈Wj\in W. Constant-degree sum-of-squares barrier conjecture. If σ≤1−α/4\sigma\leq1-\alpha/4 and c>0c>0, then the degree-O(1)O(1) sum-of-squares method cannot prove

∣W∣≲Nα+1−2σ−c.|W|\lesssim N^{\alpha+1-2\sigma-c}.

The claim is attributed to the cited work of D'Hart and collaborators and is presented as a conjectural limitation of constant-degree sum-of-squares proofs; the supplied text gives no resolution.

References

Primary source

Larry Guth, “Large value estimates in number theory, harmonic analysis, and computer science”, arXiv:2503.07410 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.