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

From papers

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 vRNv\in\mathbb R^N satisfy v1\|v\|_\infty\leq1, and suppose (Mranv)jNσ|(M_{ran}v)_j|\geq N^\sigma for every jWj\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

WNα+12σ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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.