A polynomial time algorithm is obtained that achieves a $(k/2^k)-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, and is an extension of a recently established Gaussian comparison inequality used to resolve the Weak Simplex Conjecture in coding theory.
Abstract
Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm that achieves a $(k/2^k)$-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, due to Makarychev and Makarychev (arXiv:1206.3603). Assuming the Unique Games Conjecture, De and Mossel (arXiv:1202.5258) showed that achieving an approximation ratio better than $(k+1)/2^k$ for odd $k$ and $(k+2)/2^k$ for even $k$, is NP-hard. The main technical ingredient is an extension of a recently established Gaussian comparison inequality, used to resolve the Weak Simplex Conjecture in coding theory (arXiv:2607.14087).
The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum d...
In this note, we show that the approximation algorithm for Boolean Max $k$-CSP presented in [Makarychev and Makarychev 2014] yields a $(1-o_k(1))k/2^k$ approximation, as conjectured in [Makarychev and Makarychev 2017]. This improves the previous guarantee of $(0.626612-o_k(1))k/2^k$ from [Makarychev and Makarychev 2014...
The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto...
Takashi Horiyama, Shoon Mineyoshi, Yuto Okura et al.· 0 citations
We consider the following problems: Given two $n \times n$ tables defining binary operations $+$ and $\cdot$ on a set $S$ of $n$ elements, decide whether $(S,+,\cdot)$ forms a ring or, respectively, a field. Recently, Dudek, Fischer, Gokaj, Jin, K\"unnemann, Mao, and Redzic (STOC 2026) obtained the following two (near-...
Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H...
Zi-Jie Chen, Amin Gohari, Adel Javanmard et al.· 0 citations
PJR$^+$ is a polynomial-time verifiable proportionality axiom for approval-based committee elections, but its known polynomial-time verification procedure relies on general submodular-function minimisation. We show that its objective is a maximum-closure problem and give a direct mincut formulation of the problem on a...
Drew Springham· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
