It is shown that the approximation algorithm for Boolean Max $k$-CSP yields a $(1-o_k(1)/2^k$ approximation, as conjectured in [Makarychev and Makarychev 2017], which improves the previous guarantee of $(0.626612-o_k(1)/2^k$ and asymptotically matches the known hardness results.
Abstract
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] and asymptotically matches the known hardness results. The result is a short corollary of the Gaussian stochastic domination theorem of Mulgund.
The upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle.
We show that the uniform probability measure on copies of a nonempty graph $H$ in $K_n$ is $Cq_H\log(2e(H))$-spread, where $q_H$ is its graphic expectation threshold. Consequently, the fractional expectation threshold of $H$ is at most $Cq_H\log(2e(H))$. We remove the logarithmic factor for trees and for graphs whose a...
The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\b...
N. Balaji, M. Shirmohammadi, Sébastien Tavenas et al.· 0 citations
We prove that, for every constant $\rho>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $\rho$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $\rho<\sqrt 2$ to arbitrary constants and gives a determ...
The $k$-server conjecture states that a deterministic online algorithm can achieve competitive ratio $k$ on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it. Our proof uses a natural algebraic representation of the work function as a matrix, which encodes...
Christian Coester, E. Koutsoupias, Marek Zbysinski· 0 citations
We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical plan...
S. Strelchuk, Sathyawageeswar Subramanian, Adam Wesolowski· 1 citation· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
