ECCC-Report TR19-115https://eccc.weizmann.ac.il/report/2019/115Comments and Revisions published for TR19-115en-usMon, 09 Sep 2019 09:25:34 +0300
Paper TR19-115
| Parameterized Intractability of Even Set and Shortest Vector Problem |
Arnab Bhattacharyya,
Édouard Bonnet,
László Egri,
Suprovat Ghoshal,
Karthik C. S.,
Bingkai Lin,
Pasin Manurangsi,
Dániel Marx
https://eccc.weizmann.ac.il/report/2019/115The 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 A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether there is a nonzero vector x such that Ax 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.Mon, 09 Sep 2019 09:25:34 +0300https://eccc.weizmann.ac.il/report/2019/115