Simultaneously Satisfying Linear Equations Over ${\mathbb{F}}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average

R. Crowston, M. Fellows, G. Gutin +4

In the parameterized problem \textsc{MaxLin2-AA}[$k$], we are given a system with variables $x_1,...,x_n$ consisting of equations of the form ${\prod }_{i\in I}{x}_i=b$, where $x_i,b…