 License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.229
URN: urn:nbn:de:0030-drops-33416
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3341/
 Go to the corresponding LIPIcs Volume Portal

### Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average

 pdf-format:

### Abstract

In the parameterized problem MaxLin2-AA[\$k\$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {-1, 1} and I is a nonempty subset of {1,...,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+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k^2 log k) variables and can be solved in time 2^{O(k log k)}(nm)^{O(1)}. This solves an open problem of Mahajan et al. (2006).
The problem Max-r-Lin2-AA[k,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 a theorem on Max-\$r\$-Lin2-AA[k,r] which implies that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f that maps {-1,1}^n to the set of reals and whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdös bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2 +(n-1)/4 edges) and obtaining a generalization.

### BibTeX - Entry

```@InProceedings{crowston_et_al:LIPIcs:2011:3341,
author =	{Robert Crowston and Michael Fellows and Gregory Gutin and Mark Jones and Frances Rosamond and St{\'e}phan Thomass{\'e} and Anders Yeo},
title =	{{Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages =	{229--240},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-34-7},
ISSN =	{1868-8969},
year =	{2011},
volume =	{13},
editor =	{Supratik Chakraborty and Amit Kumar},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 