Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

作者：

Highlights：

• Can we satisfy more than half of a system of linear equations over GF(2)?

• Parameter is the difference between the number of satisfied and falsified equations.

• We provide a kernel and a fixed-parameter algorithm for the parameterized problem.

• This answers an open question of Mahajan et al. (2006).

摘要

•Can we satisfy more than half of a system of linear equations over GF(2)?•Parameter is the difference between the number of satisfied and falsified equations.•We provide a kernel and a fixed-parameter algorithm for the parameterized problem.•This answers an open question of Mahajan et al. (2006).

论文关键词：MaxLin,Kernel,Fixed-parameter tractable

论文评审过程：Received 15 December 2011, Revised 24 August 2013, Accepted 15 October 2013, Available online 24 October 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.10.002