On Average Baby PIH and Its Applications

Let $\mathrm{\Pi }=(X,\mathrm{\Sigma },\mathrm{\Phi })$ be a 2CSP instance with a set $X$ of variables, an alphabet $\mathrm{\Sigma }$, and a set $\mathrm{\Phi }$ of constraints. A multi-assignment $\widehat{\sigma }:X\to 2^{\mathrm{\Sigma }}$ relaxes the standard notion of assignments by assigning each variable $x\in$$X$ a set of values in $\mathrm{\Sigma }$, i.e., $\widehat{\sigma }(x)\subseteq \mathrm{\Sigma }$. Thereby, $\mathrm{\Pi }$ is said to be satisfied by $\widehat{\sigma }$ if for every constraint $\phi \in \mathrm{\Phi }$, one can pick for each variable $x$ of $\phi$ a value from the set $\widehat{\sigma }(x)$ assigned to this variable to satisfy $\phi$. We say that $\widehat{\sigma }$ assigns ${\sum }_{x\in X}|\widehat{\sigma }(x)|$ values to $X$ in total, or equivalently, each variable in $X$ is assigned $\frac{{\sum }_{x\in X}|\widehat{\sigma }(x)|}{|X|}$ values on average (see Definition 7). Our main result is the following theorem stating that the Average Baby PIH holds under $𝖶[\mathrm{𝟣}]\ne \text{FPT}$.

Clearly any standard assignment $\sigma :X\to \mathrm{\Sigma }$ can be identified with a multi-assignment $\widehat{\sigma }$ that assigns each variable $x\in X$ a set of a single value, i.e., $\widehat{\sigma }(x)=\{\sigma (x)\}$. Hence, there is a constant $r$ gap in Theorem 1 between YES and NO instances on the average number of values assigned to each variable, which gives us the aforementioned Avg-$r$-Gap-$2\mathrm{C}\mathrm{S}\mathrm{P}$ problem. On the other hand, the constant gap for the PIH is on the fraction of constraints that can be satisfied by an assignment. That is, a YES instance is a 2CSP instance whose all constraints can be satisfied by an assignment, while any assignment can only satisfy at most a constant fraction of constraints in a NO instance. So, perhaps surprisingly, the difference between the Average Baby PIH and the PIH can be pinpointed within the Avg-$r$-Gap-$2\mathrm{C}\mathrm{S}\mathrm{P}$ problem precisely in terms of whether a given instance contains a “dense” or “sparse” set of constraints.²²2This is pointed out by an anonymous reviewer. More precisely:

As a first application of the Average Baby PIH under $𝖶[\mathrm{𝟣}]\ne \text{FPT}$, using a reduction in [13], we obtain the $𝖶[\mathrm{𝟣}]$-hardness of constant approximating the $k$-ExactCover problem (see Definition 9), improving its previous approxmation lower bound under a stronger assumption, i.e., the Gap-ETH [23].

We remark that the $𝖶[\mathrm{𝟣}]$-hardness of approximating $k$-ExactCover has been a long-standing open problem in parameterized complexity. Although the $𝖶[\mathrm{𝟣}]$, $𝖶[\mathrm{𝟤}]$, ETH-hardness of approximating the $k$-SetCover problem has been established in [6, 15, 18, 20], as a special case of $k$-SetCover, the hardness of approximating $k$-ExactCover was only known under the PIH [23] prior to our work.

The second application is a close relationship between running time lower bounds for constant approximating the parameterized Nearest Codeword Problem $\gamma$-Gap-$k$-NCP_p (see Definition 10) and Avg-$r$-Gap-$2\mathrm{C}\mathrm{S}\mathrm{P}$. Its proof is a straightforward composition of two known reductions in [23, 13] .

To prove Theorem 1, we show that the $𝖶[\mathrm{𝟣}]$-hardness for the Baby PIH implies the $𝖶[\mathrm{𝟣}]$-hardness for the Average Baby PIH. Here, the “$𝖶[\mathrm{𝟣}]$-hardness for the Baby PIH” means that, for all $r>1$, it’s $𝖶[\mathrm{𝟣}]$-hard to decide whether (i) a 2CSP instance is satisfiable, or (ii) it cannot be satisfied by any multi-assignment assigning each variable no more than $r$ values. Thus there is a constant $r$ gap between (i) and (ii) in the number of values assigned to each variable. Thereby, the gap is “local.” As already mentioned, for the Average Baby PIH, the gap is on the average number of values, or equivalently, the total number of values assigned to all the variables. Hence, the gap is “global.” Our reduction from the Baby PIH to the Average Baby PIH is thus said to be “local-to-global.”

Technically, our reduction relies on a simple but crucial property of high-distance error-correcting codes (ECC) shown in [16, 20]. In particular, we need an ECC $𝒞\subseteq {𝔽}_p^m$ with relative distance $1-\delta$ such that any two distinct codewords $x,y\in 𝒞$ can agree on at most $\delta m$ entries. So if we have a set $S$ of codewords and an $\epsilon$-fraction of entries (denoted by $I\subseteq [m]$) with $\epsilon \gg \delta$ such that for each $i\in I$, we can find distinct $x,y\in S$ that agree on their $i$-th entry, then the size of $S$ must be large. The lower bound of $|S|$ is called the collision number of $𝒞$, denote by ${\mathrm{Col}}_{\epsilon }(𝒞)$. A simple counting argument in [20] shows that ${\mathrm{Col}}_{\epsilon }(𝒞)\ge \sqrt{2\epsilon /\delta }$.

Now given a 2CSP instance ${\mathrm{\Pi }}_0=(X_0,{\mathrm{\Sigma }}_0,{\mathrm{\Phi }}_0)$, let $n=|{\mathrm{\Pi }}_0|>|{\mathrm{\Sigma }}_0|$, parameter $k=|X_0|$, and $k^{\prime }=|{\mathrm{\Phi }}_0|$. We fix some ECC with very large relative distance (e.g., a Reed-Solomon code) $𝒞:{𝔽}_p^k\to {𝔽}_p^{k^{\prime \prime }}$ for prime and $k^{\prime \prime }=\mathrm{\Theta }(k^5)$. Then we have ${\mathrm{Col}}_{\epsilon }(𝒞)>2rk$. We construct a new 2CSP instance $\mathrm{\Pi }=(X_1\dot{\cup }{X}_2,\mathrm{\Sigma },\mathrm{\Phi })$ as:

• $\mathrm{■}$

  $X_1=\{u_1,\mathrm{\cdots },u_{k^{\prime }}\}$, $X_2=\{v_1,\mathrm{\cdots },v_{k^{\prime \prime }}\}$.

• $\mathrm{■}$

  Each $u_j$ takes value from the (encoding of) satisfying assignments of ${\phi }_j=(x_{i_1}{x}_{i_2},C_j)\in {\mathrm{\Phi }}_0$, i.e., $\{(𝒞(a_1),𝒞(a_2)):(a_1,a_2)\in C_j\}$. Each $v_{\mathrm{\ell }}$ takes value from ${𝔽}_p^k$.

• $\mathrm{■}$

  For each $u_j\in X_1$ and $v_{\mathrm{\ell }}\in X_2$, there is a constraint that checks whether $u_j$’s assigned value $(w_1,w_2)$ and $v_{\mathrm{\ell }}$’s assigned value $s$ satisfy $w_1[\mathrm{\ell }]=s[i_1]$ and $w_2[\mathrm{\ell }]=s[i_2]$.

See Figure 1 for an illustration. Finally, we duplicate $X_1$ and $X_2$ each an appropriate number of times to make them equal in size, finishing our reduction.

In general, an assignment to $X_1$ should correspond to a satisfying multi-assignment to the original instance ${\mathrm{\Pi }}_0$, and the value assigned to each $v_{\mathrm{\ell }}\in X_2$ is a “guess” of the $\mathrm{\ell }$-th entry of the encoding of every $x_i$. It is easy to see that if the input instance ${\mathrm{\Pi }}_0$ is satisfiable, then so does the new 2CSP instance $\mathrm{\Pi }$, since for each $u_j\in X_1$ corresponding to ${\phi }_j=(x_{i_1}{x}_{i_2},C_j)$, we can simply assign it the value $(𝒞(\sigma (x_{i_1})),𝒞(\sigma (x_{i_2})))$, where $\sigma$ is a satisfying assignment for ${\mathrm{\Pi }}_0$. At the same time, the value assigned to each $v_{\mathrm{\ell }}\in X_2$ is $(𝒞(\sigma (x_1))[\mathrm{\ell }],\mathrm{\cdots },𝒞(\sigma (x_k))[\mathrm{\ell }])\in {𝔽}_p^k$.

For soundness, suppose ${\mathrm{\Pi }}_0$ has no satisfying multi-assignment assigning at most $r$ values to each variable, we need to argue that $\mathrm{\Pi }$ has no satisfying multi-assignment that assigns $r(1-\epsilon )(|X_1|+|X_2|)/2$ values in total. To that end, we exploit the collision number of the code $𝒞$. Fix any satisfying multi-assignment $\widehat{\sigma }$ to $\mathrm{\Pi }$. Recall that each variable $u_j\in X_1$ is assigned some value from a satisfying partial assignment to ${\phi }_j\in {\mathrm{\Phi }}_0$. Then, $\widehat{\sigma }(X_1)$ naturally gives a satisfying multi-assignment to ${\mathrm{\Pi }}_0$, which implies that there exists a variable $x_i\in X_0$ such that more than $r$ different values are assigned by $\widehat{\sigma }$ to $u_j$, for which the corresponding constraint ${\phi }_j$ contains $x_i$.

Now we have two possible cases for $\widehat{\sigma }$. In the first case, for $(1-\epsilon )$-fraction of variables in $X_2$, the multi-assignment $\widehat{\sigma }$ assigns each of them more than $r$ values. We are done, since this implies that the total number of assigned values by $\widehat{\sigma }$ is more than $(1-\epsilon )r|X_2|$. For the second case, there exists an $\epsilon$-fraction of variables in $X_2$, each of which is assigned by $\widehat{\sigma }$ at most $r$ values. Given such a variable $v_{\mathrm{\ell }}$, we have more than $r$ different codewords assigned to $X_1$ in $x_i$’s position which has at most $r$ possible values in the $\mathrm{\ell }$-th entry. This entails the existence of two different codewords with the same $\mathrm{\ell }$-th entry. Since there are $\epsilon m$ such entries, the assignment to $X_1$ must contain at least ${\mathrm{Col}}_{\epsilon }(𝒞)$ different codewords. Each assignment to $u_j\in X_1$ contributes two codewords, so the total number of assigned values by $\widehat{\sigma }$ is at least ${\mathrm{Col}}_{\epsilon }(𝒞)/2>rk$. In summary, both cases guarantee a constant gap on either $X_1$ or $X_2$, showing that any satisfying multi-assignment to $\mathrm{\Pi }$ must assign $r(1-\epsilon )(|X_1|+|X_2|)/2$ values to $X_1\cup X_2$ in total.

More details are referred to Section 3.

For minimization problems, the technique of constructing two parts of variables and arguing that at least one part has a large gap seems quite general, as exhibited by the previous works showing the $𝖶[\mathrm{𝟣}]$-hardness of approximating $k$-SetCover [6, 20] and $k$-NCP [17]. The use of the collision number of error-correcting codes in the context of parameterized inapproximability was first introduced in [16] and further developed in [20, 17]. We ask whether these techniques can be unified.

We also suggest two new variants of the Average Baby PIH, which might serve as a next step towards proving the PIH under $𝖶[\mathrm{𝟣}]\ne \text{FPT}$. On closer inspection of our construction, particularly Case 1 in the proof of Lemma 20, it only guarantees the total number of values assigned to $X_1$ (i.e., ${\mathrm{\Sigma }}_{x\in X_1}|\widehat{\sigma }(x)|$) is large. This could happen if an $o(1)$-fraction of $x$’s in $X_1$ is assigned super-constant number of values. We ask if a larger gap can be achieved. So the first one asks whether the Average Baby PIH can be strengthened by requiring a constant fraction of variables to be assigned multiple values.

We remark that the case of $r=2$ follows from the inapproximability of $k$-Clique [19, 14, 5].

The second variant is already contained in Theorem 2, thus equivalent to PIH.

It is also interesting to consider whether the inapproximability factor in the Average Baby PIH can be improved to $\omega (1)$, since this would directly lead to better lower bounds for approximating $k$-ExactCover. The current obstacle is that, although the running time of our reduction does not depend on the approximation factor, our reduction relies on the gap created in the Baby PIH [13]. In order to achieve an $r$-gap in the Baby PIH, the reduction in [13] runs in time $\mathrm{\Omega }(n^{{(2r)}^r})$, consequently, the existing FPT reduction cannot create a super-constant $r=\omega (1)$ gap .

In Section 2, we introduce the main computational problems and complexity assumptions studied in this paper. As the central contribution, Section 3 explains our reduction from the Baby PIH to the Average Baby PIH. This, in fact, establishes the Average Baby PIH under $𝖶[\mathrm{𝟣}]\ne \text{FPT}$. In Appendix A, we present a reduction from Avg-$r$-Gap-$2\mathrm{C}\mathrm{S}\mathrm{P}$ to the constant approximation of $k$-ExactCover, which slightly differs from the construction in [13].

The approximation of parameterized 2CSP refers to the following problem.

As already mentioned, the notion of multi-assignment extends the usual assignment in such a way that each variable can be assigned multiple values.

Let $r\ge 1$. We say that a 2CSP instance $\mathrm{\Pi }=(X,\mathrm{\Sigma },\mathrm{\Phi })$ is $r$-list satisfiable if there exists a multi-assignment $\widehat{\sigma }$ with individual size no more than $r$ which satisfies $\mathrm{\Pi }$, and $\mathrm{\Pi }$ is $r$-average list satisfiable if there exists a multi-assignment $\widehat{\sigma }$ with total size no more than $r|X|$ which satisfies $\mathrm{\Pi }$.

We also consider the $k$-ExactCover problem (aka, the $k$-UniqueSetCover problem) and the $k$-NCP problem (aka, $k$-MLD, for the parameterized Maximum Likelihood Decoding problem) as defined below.

The Baby PIH, a hypothesis implied by PIH, asserts the hardness of approximating individual size of a satisfying multi-assignment. Formally,

We emphasize that the Baby PIH is a hardness hypothesis with a local condition, i.e., the individual size of satisfying assignments. It is shown that the standard assumption $𝖶[\mathrm{𝟣}]\ne \text{FPT}$ implies the Baby PIH:

In contrast, the Average Baby PIH is defined on a global condition concerning the total size of satisfying assignments. The precise statement of this complexity assumption contains a technical property on the “shape” of the constraints in a 2CSP instance.

Some explanation for “rectangular” might be in order. Recall that a subset $S\subseteq {\mathrm{\Sigma }}^2$ is a (combinatorial) rectangle if and only if there exist $A,B\subseteq \mathrm{\Sigma }$ such that $S=A\times B$. It is easy to verify that $R\subseteq {\mathrm{\Sigma }}^2$ is rectangular if and only if $R$ is the union of a set of pairwise disjoint rectangles.

We employ a local-to-global reduction developed in [17] to amplify the local gap for one variable (Theorem 13) into a global gap for all variables, thus proving the Average Baby PIH from the Baby PIH.

To show Theorem 16, we first introduce some tools from coding theory. The collision number of an error-correcting code characterizes the number of codewords needed to find “collision” on a constant fraction of coordinates. We use the definition in [17]:

For Reed-Solomon codes, we have the following lower bounds on their collision number.

Our proof of Theorem 16 consists of two reductions. The first one (Lemma 20) reduces $2$CSP instances from the Baby PIH, i.e., with a “local” gap as explained in Section 1.2, to a new instance whose constraints are between two disjoint groups of variables. The new instance has a different “global” gap on each group of variables. As the sizes of the two groups might not be balanced, we do not necessarily have a “global” gap on all the variables. But this is easily remedied by the second reduction (Lemma 22) which makes an appropriate number of copies of the two groups.