On Approximability of Satisfiable k-CSPs: III

Amey Bhangale, Subhash Khot, Dor Minzer

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

Abstract

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property also holds for low-degree functions as low-degree functions become a constant function under a random restriction with a non-negligible probability. We show that this essentially is the only possible reason. More specifically, we show that the function must be correlated to a product of a linear function and a low-degree function. One of the main motivations of studying this question comes from the recent work of the authors towards understanding approximability of satisfiable Constraint Satisfaction Problems. Towards proving our structural theorem, we analyze a 2-query direct product test for the table F: [n] qn → {0,1}qn where q (0,1). We show that, for every constant ϵ>0, if the test passes with probability ϵ>0, then there is a global function g: [n]→ {0,1} such that for at least-(ϵ) fraction of sets, the global function g agrees with the given table on all except α(ϵ) many locations. The novelty of this result lies in the fact that α(ϵ) is independent of the set sizes. Prior to our work, such a conclusion (in fact, a stronger conclusion with α = 0) was shown by Dinur, Filmus, and Harsha albeit when the test accepts with probability 1-ϵ for a small constant ϵ>0. The setting of parameters in our direct product tests is fundamentally different compared to the previous results and hence our analysis involves new techniques, including the use of the small-set expansion property of graphs defined on multi-slices. As one application of our structural result, we give a 4-query linearity test under the p-biased distribution. More specifically, for any p (1/3,2/3), we give a test that queries a given function f: {0,1}n → {0,1} at 4 locations, where the marginal distribution of each query is μp-n. The test has perfect completeness and soundness 1/2+ϵ-in other words, for every constant ϵ>0, if the test passes with probability at least 1/2+ϵ, then the function f is correlated to a linear function under the μp-n measure. This qualitatively improves the results on the linearity testing under the p-biased distribution from the previous work where the authors studied the test with soundness 1-ϵ, for ϵ close to 0.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages643-655
Number of pages13
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

Keywords

  • constraint satisfaction problems
  • direct product test
  • hardness of approximation
  • linearity test

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'On Approximability of Satisfiable k-CSPs: III'. Together they form a unique fingerprint.

Cite this