Approximation Resistant Predicates From Pairwise Independence

2008/02/15 by Per Austrin, Austrin, Per, Elchanan Mossel +1 · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.0802.2300

arxiv created 2008/02/15 · openalex publication_date 2008/02/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the approximability of predicates on k variables from a domain [q], and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate P is approximation resistant if there exists a balanced pairwise independent distribution over [q]^k whose support is contained in the set of satisfying assignments to P.

Cited by

• Improved Hardness Results for Nash Social Welfare, Budgeted Allocation and GAP via the Unique Games Conjecture

Related

• A Characterization of Approximation Resistance
• A Characterization of Approximation Resistance for Even k-Partite CSPs
• On the Approximation Resistance of Balanced Linear Threshold Functions
• Refuting Unique Game Conjecture
• On the Usefulness of Predicates