EUVIMEDEUVIMED entdecken
Crossref

On Approximability of Satisfiable k-CSPs: V

Amey Bhangale, Subhash Khot, Dor Minzer

TheoretiCS · 20.05.2026 · Volume 5

DOI: 10.46298/theoretics.26.9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, online erschienen am 20.05.2026. Verfasst von Amey Bhangale und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs. Our framework is based on a new hybrid approximation algorithm, which uses a combination of the Gaussian elimination technique (i.e., solving a system of linear equations over an Abelian group) and the semidefinite programming relaxation. We complement our algorithm with a matching dictator vs. quasirandom test that has perfect completeness. The analysis of our dictator vs. quasirandom test is based on a novel invariance principle, which we call the mixed invariance principle. Our mixed invariance principle is an extension of the invariance principle of Mossel, O'Donnell and Oleszkiewicz [Annals of Mathematics, 2010] which plays a crucial role in Raghavendra's work. The mixed invariance principle allows one to relate 3-wise correlations over discrete probability spaces with expectations over spaces that are a mixture of Guassian spaces and Abelian groups, and may be of independent interest. 89 pages. This is the TheoretiCS journal version

Zitieren

APA

Bhangale, A., Khot, S., & Minzer, D. (2026). On Approximability of Satisfiable k-CSPs: V. TheoretiCS, Volume 5. https://doi.org/10.46298/theoretics.26.9

Vancouver

Bhangale A, Khot S, Minzer D. On Approximability of Satisfiable k-CSPs: V. TheoretiCS. 2026;Volume 5. doi:10.46298/theoretics.26.9

BibTeX
@article{Bhangale2026,
  author = {Bhangale, Amey and Khot, Subhash and Minzer, Dor},
  title = {On Approximability of Satisfiable k-CSPs: V},
  journal = {TheoretiCS},
  year = {2026},
  volume = {Volume 5},
  doi = {10.46298/theoretics.26.9}
}
Kostenlos starten →