Parameterized Intractability of Even Set and Shortest Vector Problem
Open Access
- 22 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (3), 1-40
- https://doi.org/10.1145/3444942
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.
Keywords
Funding Information
- Ramanujan Fellowship DSTO (1358)
- Indo-US Joint Center for Pseudorandomness in Computer Science while at Indian Institute of Science (MOE2019-T2-1-152)
- European Research Council (725978)
- ERC-CoG (772839)
- JSPS KAKENHI (JP16H07409)
- JST ERATO (JPMJER1201)
This publication has 35 references indexed in Scilit:
- Parameterized complexity of generalized domination problemsDiscrete Applied Mathematics, 2012
- Hardness of approximating the shortest vector problem in latticesJournal of the ACM, 2005
- Approximating CVP to Within Almost-Polynomial Factors is NP-HardCombinatorica, 2003
- Hardness of approximating the minimum distance of a linear codeIEEE Transactions on Information Theory, 2003
- ApproximatingTheoretical Computer Science, 2002
- The hardness of the closest vector problem with preprocessingIEEE Transactions on Information Theory, 2001
- Approximating the SVP to within a Factor (1+1/dimε) Is NP-Hard under Randomized ReductionsJournal of Computer and System Sciences, 1999
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectorsInformation Processing Letters, 1999
- The intractability of computing the minimum distance of a codeIEEE Transactions on Information Theory, 1997
- On the inherent intractability of certain coding problems (Corresp.)IEEE Transactions on Information Theory, 1978