### Abstract

In the parameterized problem MaxLin2-AA[k ], we are given a system with variables x1,…,xnx1,…,xn consisting of equations of the form ∏i∈Ixi=b∏i∈Ixi=b, where xi,b∈{−1,1}xi,b∈{−1,1} and I⊆[n]I⊆[n], each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+kW/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0k=0). We show that MaxLin2-AA[k ] has a kernel with at most View the MathML sourceO(k2logk) variables and can be solved in time 2O(klogk)(nm)O(1)2O(klogk)(nm)O(1). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,rk,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove that Max-r-Lin2-AA[k,rk,r] has a kernel with at most (2k−1)r(2k−1)r variables.

Original language | English |
---|---|

Pages (from-to) | 687-696 |

Number of pages | 10 |

Journal | Journal of Computer and System Sciences |

Volume | 80 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jun 2014 |

## Fingerprint Dive into the research topics of 'Satisfying more than half of a system of linear equations over GF(2): A multivariate approach'. Together they form a unique fingerprint.

## Cite this

Crowston, R., Fellows, M., Gutin, G., Jones, M., Kim, E. J., Rosamond, F., Ruzsa, I. Z., ThomassÃ©, S., & Yeo, A. (2014). Satisfying more than half of a system of linear equations over GF(2): A multivariate approach.

*Journal of Computer and System Sciences*,*80*(4), 687-696. https://doi.org/10.1016/j.jcss.2013.10.002