Paper Info
Title
The Quest for Strong Inapproximability Results with Perfect Completeness
Abstract
AbstractThe Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture. This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an “almost Unique” version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we call V Label Cover. Assuming a conjecture concerning the inapproximability of V Label Cover on perfectly satisfiable instances, we prove the following implications:• There is an absolute constant c0 such that for k ≥ 3, given a satisfiable instance of Boolean k-CSP, it is hard to find an assignment satisfying more than c0k2/2k fraction of the constraints.• Given a k-uniform hypergraph, k ≥ 2, for all ε > 0, it is hard to tell if it is q-strongly colorable or has no independent set with an ε fraction of vertices, where q=⌈k+√k-1/2⌉. • Given a k-uniform hypergraph, k ≥ 3, for all ε > 0, it is hard to tell if it is (k-1)-rainbow colorable or has no independent set with an ε fraction of vertices.
Year
DOI
Venue
2021
10.1145/3459668
ACM Transactions on Algorithms
Keywords
DocType
Volume
Inapproximability, hardness of approximation, dictatorship testing, constraint satisfaction, hypergraph coloring
Journal
17
Issue
ISSN
Citations 
3
1549-6325
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Joshua Brakensiek126.80
V. Guruswami23205247.96