For random Boolean k-ary constraint satisfaction problems, particularly for odd k, does the Sherali–Adams hierarchy achieve refutation guarantees comparable to those obtained by the stronger sum-of-squares hierarchy? Equivalently, for a prescribed Sherali–Adams degree, can the constraint-density requirement for strong refutation be reduced polynomially in n relative to the bound of O’Donnell and Schramm?

O’Donnell–Schramm Sherali–Adams question

The question asks whether Sherali–Adams can match refutation guarantees previously obtained using stronger sum-of-squares methods. O’Donnell and Schramm’s work established major affirmative results for graphs and random constraint-satisfaction problems.

Known results

O’Donnell and Schramm (2017; journal publication 2021): Sherali–Adams certifies strong maximum-cut bounds under a random-walk eigenvalue condition.
Their results give constant-round certification for random graphs with about $n^{1.01}$ edges and subpolynomial rounds for graphs with $n\operatorname{polylog}(n)$ edges.
They also obtain constant-round strong refutation of random Boolean $k$ -CSPs with $n^{\lceil k/2\rceil+\delta}$ constraints.
The work includes corresponding results for independent set, maximum clique, and vertex cover.

August 2026 claimed resolution

Raghu Meka and Eli Putterman’s preprint claims an approximate Cauchy–Schwarz inequality that supplies the missing ingredient and yields a polynomial improvement in the constraint-density requirement for Sherali–Adams refutation of semirandom CSPs. It is unrefereed, so the claimed resolution remains unverified.

Current status (as of August 2026): The earlier Sherali–Adams bounds are established, while Meka and Putterman’s stronger claimed resolution awaits independent verification.

O’Donnell–Schramm Sherali–Adams question

Progress summary

Primary source

Additional references

Solutions 0