Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. +1

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 $\m…