Parameterized Intractability of Even Set

Abstract: The k-Even Set problem is a parameterized variant of the Minimum Distance Problem
for binary ?linear codes, 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. Here, k is the parameter of the problem. The question of whether
k-Even Set is fixed parameter tractable (FPT) has been repeatedly raised in
literature and has earned its place in Downey and Fellows' book (2013) as
one of the "most infamous" open problems in the field of Parameterized
Complexity.

In this talk, I will present our work showing
that k-Even Set does not admit FPT algorithms under the (randomized) Gap
Exponential Time Hypothesis (Gap-ETH). In fact, our result rules out not
only exact FPT algorithms, but also any constant factor FPT approximation
algorithms for the problem. Furthermore, our result holds even under the
following weaker assumption, which is also known as the Parameterized
Inapproximability Hypothesis (PIH): no (randomized) FPT algorithm can
distinguish a satisfiable 2CSP instance from one which is only
0.99-satisfiable (where the parameter is the number of variables).

?In a subsequent work, Bonnet, Egri, Lin and Marx showed inapproximability
of the parameterized Nearest Codeword problem, which together with our
result, implies unconditional W[1]-hardness of Even Set. If there is time,
I will also sketch this result.?

Joint work with Karthik C.S., Suprovat Ghoshal and Pasin Manurangsi.