Hot answers tagged

8

Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$: The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ approximation [MM14 and MNT16]. For $k = \Omega(q)$, there is a matching hardness of $O(kq/q^k)$ by Håstad (UGC-hardness) and Chan (NP-hardness) [Chan13]. For $k$ ...


6

You are probably looking for this paper: Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6 In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms. This includes CSPs as a special case of ...


5

For the intermediate question (a core with three top-bottom runs), how about this? Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some ...


4

This of course depends on the type of satisfaction problems you are trying you encode in SAT. Assuming the general case, where your problem falls into the class of problems that can be handled by some existing encoding techniques (a review of some techniques can be found in [1]), some techniques are specific to support encoding quadratic constraints (and ...


4

Section 1 of the paper, in which the first definition appears, is introductory. The formal development starts at Section 2. The part of the paper starting at Section 2 is completely self-contained. Therefore, if there is any mismatch between a definition in Section 1 and a definition elsewhere, the latter is the correct one. In theoretical computer science, ...


4

Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input) since there is a linear relation between ghw and hw [1]: $\mathsf{hw} \leq 3\mathsf{ghw}+1$. So basically, you can see hw as a easier to compute constant approximation of ghw. I am not aware however of ...


2

The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.


2

Concerning the question whether Shaefer’s dichotomy theorem (or more generally, the Feder–Vardi conjecture, recently proved by Bulatov and Zhuk) can be generalized to promise problems: the complexity of promise CSPs is currently a hot research topic. It is still very much open if there is such a dichotomy even for Boolean PCSPs. However, partial results are ...


2

If the SAT instance has a unique solution then you are asking for the actual solution. Given the Valiant–Vazirani randomized reduction from SAT to unique SAT, if there was a way of efficiently estimating the probability distribution of variables then you could use it to solve SAT.


2

So if I understood well, your problem in the language of graph theory would be as follows: Is there a $k$ such that if for a $3$-uniform hypergraph for any $k$ of its edges we can select a $1$-shallow hitting set (a set of vertices that meets each of the $k$ edges in exactly one vertex), then the hypergraph is $2$-colorable? The answer to this question ...


1

Following Emil's suggestion and using trial and error, define $P'(x_1, x_2, x_3, x_4) \equiv P(-x_1, x_2, x_3, x_4)$ Instances of $\text{CSP}(P')$ are isomorphic to instances of $\text{CSP}(P)$, via adding a negation in every constraint where $x_1$ appears. Then we apply the theorem on $P'$ after checking that the $\{3,4\}$ fourier coefficient is still ...


Only top voted, non community-wiki answers of a minimum length are eligible