Parameterized Intractability of Even Set and Shortest Vector Problem

• Published in: arXiv.org 2019-09
• Main Authors: Bhattacharyya, Arnab, Bonnet, Édouard, Egri, László, Ghoshal, Suprovat, Karthik, C S, Lin, Bingkai, Pasin Manurangsi, Marx, Dániel
• Format: Article
• Language: English
• Subjects: Complexity; Integers; Parameterization; Questions; Randomization
• ISSN: 2331-8422

The \(k\)-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over \(\mathbb F_2\), which can be stated as follows: given a generator matrix \(\mathbf A\) and an integer \(k\), determine whether the code generated by \(\mathbf A\) has distance at most \(k\), or in other words, whether there is a nonzero vector \(\mathbf{x}\) such that \(\mathbf A \mathbf{x}\) has at most \(k\) nonzero coordinates. The question of whether \(k\)-Even Set is fixed parameter tractable (FPT) parameterized by the distance \(k\) has been repeatedly raised in literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows (1999). In this work, we show that \(k\)-Even Set is W[1]-hard under randomized reductions. 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 \(\ell_p\) norm for some fixed \(p\)) is at most \(k\). Similar to \(k\)-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any \(p > 1\), \(k\)-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.