Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Abstract

This paper resolves two long-standing open problems in parameterized complexity by establishing the intractability of the $k$-Even Set (Minimum Distance Problem) and the $k$-Shortest Vector Problem ($k$-SVP). By leveraging the (randomized) Gap Exponential Time Hypothesis (Gap-ETH), the authors demonstrate that these problems do not admit Fixed-Parameter Tractable (FPT) algorithms and are, in fact, hard to approximate within constant factors. This work provides the first definitive evidence of hardness for these "infamous" problems, which had resisted classification for decades.

Introduction

In computational complexity, NP-hard problems are generally viewed as intractable. However, Parameterized Complexity provides a more granular lens, asking whether a problem can be solved efficiently if a specific parameter $k$ (such as the size of the solution) remains small. Problems that can be solved in $f(k) \cdot n^{O(1)}$ time are classified as Fixed-Parameter Tractable (FPT).

For over twenty years, two specific problems remained at the top of the "most wanted" list for complexity classification: the $k$-Even Set problem and the $k$-Shortest Vector Problem ($k$-SVP). While their general versions were known to be NP-hard, their status in the parameterized hierarchy (whether they were FPT or W[1]-hard) remained unknown. This paper finally settles the debate, proving that both problems are intractable under the Gap Exponential Time Hypothesis.

Problem Definitions

1. $k$-Even Set (Minimum Distance Problem)

Given a generator matrix for a binary linear code, the $k$-Even Set problem asks whether there exists a non-zero codeword with a Hamming weight of at most $k$. This is equivalent to finding the minimum distance of a linear code, a fundamental problem in coding theory.

2. $k$-Shortest Vector Problem ($k$-SVP)

Given a basis for a lattice in $\mathbb{R}^n$, the $k$-SVP asks whether the shortest non-zero vector in the lattice has a length (typically in the $\ell_2$ norm) of at most $k$. This problem is central to lattice-based cryptography.

Methodology and Reduction Path

The authors construct a sophisticated chain of reductions starting from the Gap Exponential Time Hypothesis (Gap-ETH). Gap-ETH posits that no randomized subexponential time algorithm can distinguish between a fully satisfiable 3CNF formula and one that is only $(1-\epsilon)$-satisfiable.

The Reduction Chain

  1. Gap-ETH to PIH: The proof first invokes the Parameterized Inapproximability Hypothesis (PIH), which establishes the hardness of approximating 2-Constraint Satisfaction Problems (2CSPs).
  2. PIH to Nearest Versions: The authors reduce the 2CSP problem to the "Nearest" versions of the coding and lattice problems: the Nearest Codeword Problem ($k$-NCP) and the Nearest Vector Problem ($k$-NVP). They prove these are hard to approximate in FPT time.
  3. Sparse Covering Codes (SCC): The most significant technical hurdle is moving from the "Nearest" (inhomogeneous) versions to the "Shortest" (homogeneous) versions. To achieve this, the authors introduce Sparse Covering Codes. These are specialized linear codes designed to "cover" sparse vectors with high probability, allowing the reduction to map the target vector in NCP/NVP to the origin in MDP/SVP.
  4. Gap Amplification: Finally, the authors use "tensoring" techniques to amplify the hardness gap, showing that it is not only hard to find the exact solution but also hard to approximate it within any constant factor.

Key Insights

Breaking the Deadlock

The $k$-Even Set problem was famously listed as one of the "six most infamous" open problems in the foundational text by Downey and Fellows (2013). By proving its W[1]-hardness, this paper completes a major chapter in the history of parameterized complexity.

The Role of SCCs

Unlike the "locally dense codes" used in standard NP-hardness proofs, Sparse Covering Codes are specifically engineered for the parameterized regime. In this context, the target distance $k$ is significantly smaller than the block length $n$, requiring a more delicate construction to maintain the hardness properties during the reduction.

Hardness of Approximation

A critical takeaway is that these problems are hard to approximate within constant factors. For the $k$-Minimum Distance Problem, even a $100\times$ approximation is ruled out under PIH. For $k$-SVP in the Euclidean norm ($\ell_2$), the inapproximability can be amplified to any constant $\gamma \ge 1$.

Results Summary

  • $k$-Even Set / $k$-MDP: Assuming PIH, no FPT algorithm can distinguish between a code with distance $k$ and one with distance $\gamma k$ for any constant $\gamma \ge 1$.
  • $k$-SVP ($p > 1$): For $\ell_p$ norms where $p > 1$, $k$-SVP is hard to approximate to some constant factor $\gamma_p > 1$ in FPT time.
  • $k$-SVP ($p = 2$): For the Euclidean norm, the result is even stronger; the inapproximability factor can be amplified to any constant $\gamma \ge 1$.

Limitations and Future Research

Despite the breakthrough, several avenues for future work remain:

  • The $\ell_1$ Norm: The current techniques do not extend to $k$-SVP in the $\ell_1$ norm. Standard techniques for $\ell_1$ hardness often result in non-integral lattice bases, which are incompatible with the current parameterized framework.
  • Deterministic Reductions: The current proofs rely on randomized reductions. Determining whether these results hold under deterministic FPT reductions remains an open question.
  • Field Extensions: The $k$-Even Set result is currently limited to binary fields ($\mathbb{F}_2$). Extending the Sparse Covering Code construction to larger finite fields is a logical next step.
  • Tight Complexity Bounds: While the paper establishes intractability, the exact lower bounds (e.g., the precise function of $n$ and $k$ required for computation) are yet to be determined.

Summary updated

Abstract

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F_2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k. Here, k is the parameter of the problem. The question of whether k-Even Set is fixed parameter tractable (FPT) has been repeatedly raised in literature and has earned its place in Downey and Fellows' book (2013) as one of the "most infamous" open problems in the field of Parameterized Complexity. In this work, we show that k-Even Set does not admit FPT algorithms under the (randomized) Gap Exponential Time Hypothesis (Gap-ETH) [Dinur'16, Manurangsi-Raghavendra'16]. In fact, our result rules out not only exact FPT algorithms, but also any constant factor FPT approximation algorithms for the problem. Furthermore, our result holds even under the following weaker assumption, which is also known as the Parameterized Inapproximability Hypothesis (PIH) [Lokshtanov et al.'17]: no (randomized) FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only 0.99-satisfiable (where the parameter is the number of variables). We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the l_p norm for some fixed p) is at most k. Similar to k-Even Set, this problem is also a long-standing open problem in the field of Parameterized Complexity. We show that, for any p > 1, k-SVP is hard to approximate (in FPT time) to some constant factor, assuming PIH. Furthermore, for the case of p = 2, the inapproximability factor can be amplified to any constant.
BibTeX
@article{bhattacharyya2018parameterized,
  author = {Arnab Bhattacharyya and Suprovat Ghoshal and Karthik C. S. and Pasin Manurangsi},
  title = {{Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH}},
  journal = {Electron. Colloquium Comput. Complex.},
  year = {2018},
}
Figure