The complexity of somewhat approximation resistant predicates

Subhash Khot, Madhur Tulsiani, Pratik Worah

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


A boolean predicate f:{0,1}k → {0,1} is said to be somewhat approximation resistant if for some constant τ > |f-1(1)|/ 2k, given a τ-satisfiable instance of the MAX k-CSP(f) problem, it is NP-hard to find an assignment that strictly beats the naive algorithm that outputs a uniformly random assignment. Let τ(f) denote the supremum over all τ for which this holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates, we give a characterization of the hardness gap (τ(f)-|f-1(1)|/2k) up to a factor of O(k5). We show that the hardness gap is determined by two factors: - The nearest Hamming distance of f to a function g of Fourier degree at most 2, which is related to the Fourier mass of f on coefficients of degree 3 or higher. - Whether f is monotonically below g. When the Hamming distance is small and f is monotonically below g, we give an SDP-based approximation algorithm and hardness results otherwise. We also give a similar characterization of the integrality gap for the natural SDP relaxation of MAX k-CSP(f) after Ω(n) rounds of the Lasserre hierarchy.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
EditionPART 1
ISBN (Print)9783662439470
StatePublished - 2014
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: Jul 8 2014Jul 11 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The complexity of somewhat approximation resistant predicates'. Together they form a unique fingerprint.

Cite this