(2021) Parameterized Intractability of Even Set and Shortest Vector Problem.
|
Text
3444942.pdf Download (952kB) | Preview |
Abstract
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix and an integer , determine whether the code generated by has distance at most , or, in other words, whether there is a nonzero vector such that has at most nonzero coordinates. The question of whether -Even Set is fixed parameter tractable (FPT) parameterized by the distance has been repeatedly raised in the 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 -Even Set is W[1]-hard under randomized reductions. We also consider the parameterized -Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer , and the goal is to determine whether the norm of the shortest vector (in the norm for some fixed ) is at most . Similar to -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 , -SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.
| Item Type: | Article |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Depositing User: | Dániel Marx |
| Date Deposited: | 29 Apr 2022 09:04 |
| Last Modified: | 29 Apr 2022 09:44 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3626 |
Actions
Actions (login required)
 |
View Item |