Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

Venkatesan Guruswami, Jun Ting Hsieh, Pravesh K. Kothari, Peter Manohar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst case and average case input models, where the input is generated by (1) choosing an arbitrary planted assignment x*, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution 'shifted by x*' so that x*satisfies each constraint. For an n variable semirandom planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a o(1)-fraction of constraints, provided that the instance has at least Õ(nk/2) constraints. This matches, up to polylog (n) factors, the clause threshold for algorithms that solve fully random planted CSPs [23], as well as algorithms that refute random and semirandom CSPs [1], [4]. Our result shows that despite having worst case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst case, where analogous results require O(nk) constraints [7], [26]. Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices - reminiscent of the classical spectral sparsification - which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Pages307-327
Number of pages21
ISBN (Electronic)9798350318944
DOIs
StatePublished - 2023
Externally publishedYes
Event64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States
Duration: Nov 6 2023Nov 9 2023

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz
Period11/6/2311/9/23

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Expander Decomposition
  • Semirandom CSPs
  • Spectral Sparsification

Fingerprint

Dive into the research topics of 'Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold'. Together they form a unique fingerprint.

Cite this