Parameterized Intractability of Even Set and Shortest Vector Problem

DOI10.1145/3444942MaRDI QIDQ5056405zbMATH OpenOpenAlexFDO

Authors Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.01986

zbMATH Keywords

even setinapproximabilityminimum distance problemparameterized complexityshortest vector problem

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Linear codes (general theory) (94B05)

Abstract: 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 $mathbfA$ and an integer $k$, determine whether the code generated by $mathbfA$ has distance at most $k$, or in other words, whether there is a nonzero vector $mathbfx$ such that $mathbfAmathbfx$ 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 $el{l}_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.

Recommendations

• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• A note on the concrete hardness of the shortest independent vector in lattices
• (Gap/S)ETH hardness of SVP
• Hardness of approximating the shortest vector problem in lattices

Cited in

(14)

• Parameterized complexity of small weight automorphisms and isomorphisms
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
• Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
• Applications of random algebraic constructions to hardness of approximation
• Parameterized inapproximability hypothesis under ETH
• On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
• Approximating the number of relevant variables in a parity implies proper learning
• Parameterized complexity of feature selection for categorical data clustering
• On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP
• Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
• Parameterized approximability for modular linear equations
• Sampling with a black box: faster parameterized approximation algorithms for vertex deletion problems

This page was built for publication: Parameterized Intractability of Even Set and Shortest Vector Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056405)