On the Hardness of the One-Sided Code Sparsifier Problem

Oveis Gharan and Sahami [5] present a proof that 1. implies 2., which we will briefly reproduce here for completeness. Suppose that $h^{\ast }\in H^{\ast }$ is a string of maximal weight among strings in $H$, and suppose that $h^{\ast }$ is not $\frac{1}{2}$-thick with respect to $𝒞$; that is, $\exists c\in 𝒞$ such that . Take the string $h^{\prime }=h^{\ast }+c$, noting that $h^{\prime }\in H$. We must have that $\text{wt}(h^{\prime })>\text{wt}(h^{\ast })$, since – adding $c$ turns more coordinates of $h^{\ast }$ to one than it turns to zero. This contradicts the assumption that $h^{\ast }$ is of maximal weight among strings in $H$; hence, $h^{\ast }$ is $\frac{1}{2}$-thick with respect to $𝒞$.

Now, to show that 2. implies 1., suppose that $h\in H$ is a $\frac{1}{2}$-thick string, and that there is some $h^{\ast }\in H$ such that $\text{wt}(h^{\ast })>\text{wt}(h)$. Then consider the codeword $c=h^{\ast }+h$, with $c\in 𝒞$. Since $c+h=h^{\ast }$, and $\text{wt}(h^{\ast })>\text{wt}(h)$, we must have that ; hence, . Then $h$ is not $\frac{1}{2}$-thick, a contradiction; any $\frac{1}{2}$-thick string must be of maximal weight among its equivalence class. $◀$

To show that 1. implies 3., take some $h^{\ast }\in H$ of maximal weight, and suppose that there exists some codeword $c\in 𝒞$ such that . Then, noting that for any $a\in {𝐅}_2^n$, $\text{wt}(a)=n-\text{wt}(\overline{a})=n-\text{wt}(a+\mathrm{𝟏})$, we have that:

Hence $c+h^{\ast }$ is an element of $H$ of greater weight than $h^{\ast }$, a contradiction. More intuitively, if $\overline{h^{\ast }}$ is closer to $c$ than to $\mathrm{𝟎}$, it must be the case that it shares more coordinates with $c$ than it has zero coordinates. Then $h^{\ast }$ must differ on more coordinates with $c$ than it has nonzero coordinates – so $h^{\ast }+c$, the string consisting of all coordinates in which $h^{\ast }$ and $c$ differ, must be of higher weight than $h^{\ast }$ itself. So $\mathrm{𝟎}$ must be a nearest codeword in $𝒞$ to $\overline{h^{\ast }}$.

To show that 3. implies 1., suppose that $h\in H$ is of less than maximal weight; that is, there is some $h^{\ast }\in H$ with $\text{wt}(h^{\ast })>\text{wt}(h)$. Then $c=h^{\ast }+h$ is a codeword in $𝒞$ which is closer to $\overline{h}$ than $\mathrm{𝟎}$:

So $\mathrm{𝟎}$ is not a nearest codeword to $\overline{h}$; if $\mathrm{𝟎}$ is a nearest codeword to some $\overline{h^{\ast }}$ with $h^{\ast }\in H$, $h^{\ast }$ is of maximal weight among elements of $H$. $◀$

This concludes the proof of Theorem 5.

The fundamental property at hand here is that the operation of shifting by some constant string is an isometry; once the nearest (or furthest) codewords of one element $h$ of a coset $H$ have been determined, the nearest codewords of every other element $h^{\prime }$ in $H$ are fully determined by the difference between $h$ and $h^{\prime }$. Thus, since any element in the coset $H$ must have some nearest codewords, there must be some elements of $H$ which have any particular codeword as their nearest codeword – if $h\in H$ has $c$ as a nearest codeword, $h+(c+c^{\prime })$ has $c^{\prime }$ as a nearest codeword. The elements of $\mathrm{𝟏}+H$ which are closest to $\mathrm{𝟎}$ – corresponding to the elements of $H$ which are furthest from $\mathrm{𝟎}$ – must therefore not merely be closer to $\mathrm{𝟎}$ than any other element of $\mathrm{𝟏}+H$, but also closer to $\mathrm{𝟎}$ than they are to any other element of $𝒞$. This allows us to extract from $H^{\ast }$ knowledge of the nearest codewords of every element of $\mathrm{𝟏}+H$:

Take any $h\in H$ and $h^{\ast }\in H^{\ast }$, and suppose that there exists some string $c\in 𝒞$ such that . Then:

Since $h+c$ is in $H$, and elements of $H^{\ast }$ have maximum weight among elements of $H$, this is a contradiction; no such $c$ can exist. Furthermore, $\text{wt}(\overline{h}+(h+h^{\ast }))=n-\text{wt}(h^{\ast })$, which is the same quantity for all $h^{\ast }\in H^{\ast }$; hence, all codewords of the form $h+h^{\ast }$ have equal and minimal Hamming distance from $\overline{h}$. This proves the first direction. For the second direction, suppose that there exists a codeword $c\in 𝒞$ of minimum Hamming distance from $\overline{h}$; that is, $\text{wt}(\overline{h}+c)\le \text{wt}(\overline{h}+(h+h^{\ast }))$ for any $h^{\ast }\in H^{\ast }$. By the first direction, this is an equality; $\text{wt}(\overline{h}+c)=\text{wt}(\overline{h}+(h+h^{\ast }))$, since if then $h+h^{\ast }$ would not be a nearest codeword to $\overline{h}$. Then $\text{wt}(h+c)=\text{wt}(h^{\ast })$; as $h+c\in H$, it must be the case that $h+c\in H^{\ast }$. So $c=h+(h+c)=h+h^{\ast }$ for some $h^{\ast }\in H^{\ast }$. This proves the second direction.

Alternatively, we may observe that since $\mathrm{𝟎}$ is a nearest codeword to $\overline{h^{\ast }}$, $\mathrm{𝟎}+c=c$ must be a nearest codeword to $\overline{h^{\ast }}+c$; that is, if $c=h^{\ast }+h$, then $c$ is a nearest codeword to $\overline{h^{\ast }}+(h^{\ast }+h)=\overline{h}$. The inverse direction follows straightforwardly by reversing the argument. $◀$

This also demonstrates that, for any elements $h,h^{\prime }$ in some coset $H$ of ${𝐅}_2^n/𝒞$, the nearest codewords in $𝒞$ to $h$ are the same distance from $h$ as the nearest codewords to $h^{\prime }$. We can therefore talk about the “distance” of a coset from the code; the distance of a coset $H$ to $𝒞$ is the distance from any element of $H$ to its nearest codewords in $𝒞$. Since $\mathrm{𝟎}$ is always a codeword in any linear code, and the elements of minimum weight in a given coset must have $\mathrm{𝟎}$ as a nearest codeword, the distance of any coset is equal to the minimum weight among elements in that coset, $\text{minwt}(H)$.

Since the $\frac{1}{2}$-thick strings in a coset directly correspond to the nearest codewords of elements in that coset, we have the following:

This problem is obviously in $\mathrm{𝖭𝖯}$; we can certify any (YES) instance with a string of weight at least $k$ in the given coset. We show $\mathrm{𝖭𝖯}$-hardness by reduction from the nearest codeword problem, as defined in Section 1.

Let CosetHeavy be the problem above:

Heaviest Element Problem (CosetHeavy)
Instance: A generator matrix $M$ for a linear code $𝒞$, a string $h$ in an equivalence class $H\in {𝐅}_2^n/𝒞$, and an integer $k$.
Output: (YES) if there exists $h^{\ast }\in H$ such that $\text{wt}(h^{\ast })\ge k$, and (NO) otherwise.

We define the mapping from NCP to CosetHeavy instances as follows:

This map can obviously be computed in polynomial time.

Suppose that the NCP instance $(M,s,k)$ is a (YES) instance; there exists some $c\in 𝒞$, with $𝒞$ the linear code generated by $M$, such that $\text{wt}(c+s)\le k$. Then, specifically, the distance between $c+s$ and $\mathrm{𝟎}$ – $\text{wt}(c+s+\mathrm{𝟎})$ – is also at most $k$. So, following Theorem 8, there exists a string in the coset containing $s$ of $𝒞$ in ${𝐅}_2^n$ with weight at most $k$; there exists a string in the coset containing $\overline{s}$ with weight at least $n-k$. So the CosetHeavy instance $(M,\overline{s},n-k)$ is a (YES) instance.

Now suppose that the CosetHeavy instance is a (YES) instance. Then there is a string in the coset $H$ containing $s$ with weight at most $k$, and for any element of $H$ there is a codeword in $𝒞$ of distance at most $k$; the NCP instance is a (YES) instance.

Thus, NCP ${\le }_p$ CosetHeavy, and CosetHeavy is $\mathrm{𝖭𝖯}$-complete. $◀$

Note that this reduction is in fact surjective, and $\text{NCP}{\equiv }_p\text{CosetHeavy}$.

By Theorem 5, the $\frac{1}{2}$-thick strings with respect to a code $𝒞$ are exactly the complements of the strings which have $\mathrm{𝟎}$ as a nearest codeword – the $\frac{1}{2}$-thin strings with respect to $𝒞$. Further, the $\frac{1}{2}$-thick strings of least weight are the complements of the $\frac{1}{2}$-thin strings of greatest weight. $◀$

In fact, since the distance to the nearest codeword is constant among all elements of a given coset of $𝒞$ in ${𝐅}_2^n$, the cosets containing the optimal $\frac{1}{2}$-thin strings are those where every element is of greatest distance to their nearest codewords. The cosets containing the optimal $\frac{1}{2}$-thick strings, then, are cosets obtained by adding $\mathrm{𝟏}$ to the cosets containing the optimal $\frac{1}{2}$-thin strings (note that in a code containing the codeword $\mathrm{𝟏}$, the cosets containing the optimal $\frac{1}{2}$-thin strings are the same as the cosets containing the optimal $\frac{1}{2}$-thick strings).

We demonstrate this by polynomial-time Turing reduction from NCP. We restate the problem for convenience:

Minimal One-Sided $\frac{1}{2}$-Sparsifier Problem (OptHalfSparsifier)
Instance: A linear code $𝒞$ given by its generators.
Output: A set $S\subseteq [n]$ such that:

• $\mathrm{■}$

  (Feasibility) for all $c\in 𝒞$, $\text{wt}(c_S)\ge \frac{1}{2}c$;

• $\mathrm{■}$

  (Optimality) $S$ is of smallest size among all sets which satisfy the above.

We use Algorithm 1. This algorithm terminates in at most $n-\text{dim}(𝒞)$ calls to the OptHalfSparsifier subroutine, with $O(n-k)$ extra runtime: since $a_i\notin {𝒞}_i$ for all $i$, the dimension of ${𝒞}_{i+1}$ is one greater than the dimension of ${𝒞}_i$ for all $i$. When the dimension of ${𝒞}_i$ is $n$, then it must be the case that $s\in {𝒞}_i$; thus, the loop at line 1 is run at most $n-\text{dim}(𝒞)$ times.

It remains to show correctness. We wish to maintain the invariant that, for each $i$, the distance from $s$ to the nearest codeword in ${𝒞}_i$ is no closer than the distance from $s$ to the nearest codeword in $𝒞$. So, towards a proof by contradiction, suppose that there is some $i$ such that ${𝒞}_{i+1}$ has an element nearer to $s$ than the nearest element in ${𝒞}_i$. Note that since ${𝒞}_{i+1}={𝒞}_i\cup (a_i+{𝒞}_i)$, if ${𝒞}_{i+1}$ has an element closer to $s$ than all elements in ${𝒞}_i$, that element must be in $a_i+{𝒞}_i$. So we have:

Where, for $S\subseteq {𝐅}_2^n$, $\text{minwt}(S)$ is the smallest weight among elements of $S$. Thus, the smallest weight among elements of the coset $s+{𝒞}_i$ is larger than the smallest weight among elements of the coset $\overline{h_i^{\ast }}+{𝒞}_i$. But then the largest element in the coset $\overline{s}+{𝒞}_i$ is smaller than the largest element in the coset $h_i^{\ast }$. By Theorem 5, all largest elements of any coset are $\frac{1}{2}$-thick, and the largest element of $\overline{s}+{𝒞}_i$ is $\frac{1}{2}$-thick; thus, $h_i^{\ast }$ cannot be a $\frac{1}{2}$-thick string of minimal weight among all $\frac{1}{2}$-thick strings, a contradiction. So ${𝒞}_{i+1}$ cannot have any elements nearer to $s$ than the nearest elements in ${𝒞}_i$; by induction, ${𝒞}_i$ has no closer elements to $s$ than does $𝒞$ for any $i$.

We can see this property more intuitively by noting that adding a basis element to a linear code combines pairs of cosets which differ by that element; the maximal (minimal) elements in the resulting coset will be the maximal (minimal) elements among the two. Thus, given that the coset containing $\overline{h^{\ast }}$ contains a largest minimal element among any coset, the coset $(\overline{h^{\ast }}+{𝒞}_i)\cup (\overline{s}+{𝒞}_i)$ of ${𝒞}_{i+1}$ will contain the minimal element of $\overline{s}+{𝒞}_i$ as a minimal element; repeatedly merging cosets in this manner never moves the coset containing $s$ “closer” to the code.

Given this invariant, we proceed to show that the two conditionals on line 2 and line 3 can only be satisfied if the instance is a (YES) or (NO) instance respectively. We begin with line 2. Since $\overline{h_i^{\ast }}$ is a string of greatest distance from any codeword in ${𝒞}_i$, and has $\mathrm{𝟎}$ as a nearest codeword, if $\text{wt}(\overline{h_i^{\ast }})=n-\text{wt}(h_i^{\ast })\le k$, then the greatest distance from any string among elements in ${𝒞}_i$ is at most $k$; thus, there must be a codeword in ${𝒞}_i$ at least that close to $s$. By the invariant above, there also must be a codeword in $𝒞$ which is that close, and the NCP instance $(M,s,k)$ is a (YES) instance. To show that the conditional on line 3 is satisfied only for (NO) instances, note that if $\overline{h_i^{\ast }}+s\in {𝒞}_i$, then $s$ is in a coset with $\overline{h_i^{\ast }}$. This implies that the distance from $s$ to its nearest codewords in ${𝒞}_i$ is the same as that of $\overline{h_i^{\ast }}$ to its nearest codewords; since $\overline{h_i^{\ast }}$ has $\mathrm{𝟎}$ as a nearest codeword, the distance from $s$ to its nearest codeword is exactly $\text{wt}(\overline{h_i^{\ast }})=n-\text{wt}(h_i^{\ast })$. Since the conditional on line 2 was not satisfied, then, there exists no codeword in ${𝒞}_i$ which has distance at most $k$ from $s$. Since ${𝒞}_i\supseteq 𝒞$, there exists no codeword in $𝒞$ of at most that distance, and the NCP instance $(M,s,k)$ is a (NO) instance.

We therefore have a polynomial-time Turing reduction from NCP to OptHalfSparsifier, and OptHalfSparsifier is $\mathrm{𝖭𝖯}$-hard. $◀$

From known hardness of approximation results ([2]) of NCP, we can also derive similar results for the OptHalfSparsifier problem.

This follows directly from the algorithm above and the hardness of approximation of NCP given by Theorem 4. Suppose that instead of an algorithm which solves OptHalfSparsifier, we have an algorithm which solves the following approximation of OptHalfSparsifier:

$\gamma$-Approximate Minimal One-Sided $\frac{1}{2}$-Sparsifier Problem (${\text{ApproxOHS}}_{\gamma }$)
Instance: A linear code $𝒞$ given by its generators.
Output: A set $S\subseteq [n]$ such that:

• $\mathrm{■}$

  (Feasibility) for all $c\in 𝒞$, $\text{wt}(c_S)\ge \frac{1}{2}c$;

• $\mathrm{■}$

  (Approximate Optimality) if $S^{\ast }$ is a set which satisfies the above feasibility condition, then $\gamma \cdot |\overline{S}|\ge |\overline{S^{\ast }}|$

If $\gamma =1$, then this problem is OptHalfSparsifier. Note that the multiplicative factor here is a constraint not on the size of the set itself, but the size of its conjugate; it is trivial to find a $\frac{1}{2}$-thick set with a size within a factor of $2$ of that of the smallest $\frac{1}{2}$-thick set, by simply taking every coordinate which is represented among codewords in $𝒞$. It is easy to see from this that approximation up to a constant factor of the set size is trivial.

Given such a subroutine we can use Algorithm 1 to approximate NCP, solving the following problem:

Nearest Codeword Problem with Multiplicative Gap $\gamma$ (${\text{MultGapNCP}}_{\gamma }$)
Instance: A generator matrix $M$ for a linear code $𝒞$, a received string $s\in {𝐅}_2^n$, and an integer $k$.
Output: (YES) if there exists $c\in 𝒞$ such that $\text{wt}(c+s)\le k$. (NO) if for every $c\in 𝒞$, $\text{wt}(c+s)>\gamma k$.

To show that this reduction goes through, we follow the previous proof with a small modification: instead of maintaining that the augmented codes ${𝒞}_i$ each have no codewords closer to $s$ than the closest codewords in $𝒞$, we maintain that each ${𝒞}_i$ has no codewords outside of $𝒞$ of distance smaller than $k$ to $s$. We note first that if $h_i^{\ast }+{𝒞}_i$ has a distance from ${𝒞}_i$ at most $k$, then we will have answered (YES) during that iteration of the loop at line 1; we only proceed to add $h_i^{\ast }+s$ to the generator matrix if $h_i^{\ast }+{𝒞}_i$ is further from ${𝒞}_i$ than $k$. Thus, the set $(s+a_i+{𝒞}_i)=(\overline{h_i^{\ast }}+{𝒞}_i)$ has a distance from $𝒞$ no smaller than $k$. Formally, $\text{minwt}(s+a_i+{𝒞}_i)=\text{minwt}(\overline{h_i^{\ast }}+{𝒞}_i)>k$.

The reduction from ${\text{MultGapNCP}}_{\gamma }$ to ${\text{ApproxOHS}}_{\gamma }$ then follows from the same arguments as in the proof of Theorem 1. Briefly, if the ${\text{MultGapNCP}}_{\gamma }$ instance is a (YES) instance, then it will certainly never be the case that the distance from $s$ to ${𝒞}_i$ is greater than $k$ for any ${𝒞}_i$, so Algorithm 1 will output (YES); if the ${\text{MultGapNCP}}_{\gamma }$ instance is a (NO) instance, then, given the invariant above, Algorithm 1 may never output (YES), and must output (NO). $◀$