An Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs
2026-08-18 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors develop an approximate version of the Cauchy-Schwarz inequality that works for solutions from the Sherali-Adams linear programming hierarchy, which was previously missing. Their approach differs from earlier methods that required stronger conditions and instead uses only local positivity. This new inequality helps answer an open question from O'Donnell and Schramm’s work about refuting random constraint satisfaction problems, improving the relationship between constraints and solution complexity. Additionally, they show their findings extend to more general problem settings.
Cauchy-Schwarz inequalitySherali-Adams hierarchypseudo-distributionssum-of-squares hierarchylinear programmingsemidefinite programmingconstraint satisfaction problemspositive semidefinitenessrandom CSPrefutation
Authors
Pravesh K. Kothari, Andrew D. Lin
Abstract
We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distributions''). As a consequence, we resolve a question left open by the work of O'Donnell and Schramm [OS19] that they had explicitly attributed to the lack of such an inequality. A Cauchy-Schwarz inequality is exactly satisfied by pseudo-distributions satisfying the constraints of the sum-of-squares semidefinite programming hierarchy and already has scores of applications. However, the proof there requires global positive semidefiniteness. Our approximate version, on the other hand, relies only on local positive semidefiniteness satisfied by the Sherali-Adams pseudo-distributions. Our formulation loses an additive error that scales with the L1 norm of the coefficients of the constituent polynomials, and this loss is asymptotically tight. Our proof is elementary and relies on a simple sampling argument. As an application, we resolve a question left open in the work of O'Donnell and Schramm that gives a trade-off between constraint density and the Sherali-Adams degree for refuting random constraint satisfaction problems. Specifically, for odd arity CSPs, we show that the constraint density requirement for a given degree can be improved by a polynomial factor in $n$. Along the way, we observe that by a simple extension, the results in their work extend to a more general semirandom setting.