Search Results

Documents authored by Lin, Andrew D.

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.77
Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs

Authors: Pravesh K. Kothari and Andrew D. Lin

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

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 [Ryan O'Donnell and Tselil Schramm, 2019] 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.
Cite as

Pravesh K. Kothari and Andrew D. Lin. Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 77:1-77:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kothari_et_al:LIPIcs.APPROX/RANDOM.2026.77,
  author =	{Kothari, Pravesh K. and Lin, Andrew D.},
  title =	{{Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{77:1--77:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.77},
  URN =		{urn:nbn:de:0030-drops-277946},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.77},
  annote =	{Keywords: Sherali-Adams hierarchy, constraint satisfaction problems, semirandom CSPs, refutation, Cauchy-Schwarz inequality}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.23
Solving Random Planted CSPs Below the n^{k/2} Threshold

Authors: Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, and Peter Manohar

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We present a family of algorithms to solve random planted instances of any k-ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment x^*, and then (2) sampling constraints from a particular "planting distribution" designed so that x^* will satisfy every constraint. Given an n variable instance of a k-ary Boolean CSP with m constraints, our algorithm runs in time n^O(𝓁) for a choice of a parameter 𝓁, and succeeds in outputting a satisfying assignment if m ⩾ O(n)⋅(n/𝓁)^{k/2 - 1} log n. This generalizes the poly(n)-time algorithm of [Vitaly Feldman et al., 2015], the case of 𝓁 = O(1), to larger runtimes, and matches the constraint number vs. runtime trade-off established for refuting random CSPs by [Prasad Raghavendra et al., 2017]. Our algorithm is conceptually different from the recent algorithm of [Venkatesan Guruswami et al., 2023], which gave a poly(n)-time algorithm to solve semirandom CSPs with m ⩾ Õ(n^{k/2}) constraints by exploiting conditions that allow a basic SDP to recover the planted assignment x^* exactly. Instead, we forego certificates of uniqueness and recover x^* in two steps: we first use a degree-O(𝓁) Sum-of-Squares SDP to find some x̂ that is o(1)-close to x^*, and then we use a second rounding procedure to recover x^* from x̂.
Cite as

Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, and Peter Manohar. Solving Random Planted CSPs Below the n^{k/2} Threshold. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{basu_et_al:LIPIcs.ICALP.2026.23,
  author =	{Basu, Arpon and Hsieh, Jun-Ting and Lin, Andrew D. and Manohar, Peter},
  title =	{{Solving Random Planted CSPs Below the n^\{k/2\} Threshold}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.23},
  URN =		{urn:nbn:de:0030-drops-264127},
  doi =		{10.4230/LIPIcs.ICALP.2026.23},
  annote =	{Keywords: Random CSPs, Sparse Learning Parity with Noise}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact