[sans titre]

We consider the problem of approximating fixed-predicate constraint satisfaction problems (MAX $k$-CSP$q$($P$)), where the variables take values from $[q]=\{0,1,\ldots,q-1\}$, and each constraint is on $k$ variables and is defined by a fixed $k$-ary predicate $P$. Familiar problems like MAX $3$-SAT and MAX-CUT belong to this category. Austrin and Mossel recently identified a general class of predicates $P$ for which MAX $k$-CSP$q$($P$) is hard to approximate. They study predicates $P:[q]^k\to \{0,1\}$ such that the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs. We refer to such predicates as promising. Austrin and Mossel show that for any promising predicate $P$, the problem MAX $k$-CSP$q$($P$) is Unique-Games hard to approximate better than the trivial approximation obtained by a random assignment. We give an unconditional analogue of this result in a restricted model of computation. We consider the hierarchy of semidefinite relaxations of MAX $k$-CSP$q$($P$) obtained by augmenting the canonical semidefinite relaxation with the Sherali-Adams hierarchy. We show that for any promising predicate $P$, the integrality gap remains the same as the approximation ratio achieved by a random assignment, even after $\Omega(n)$ levels of this hierarchy. We also introduce a new general set of techniques to define consistent “local distributions” over partial assignments to variables in the problem. Defining such distributions has often been the crux of proving lower bounds on integrality gaps for hierarchies like the ones we consider.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.