**Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average.** / Crowston, Robert; Fellows, Michael; Gutin, Gregory; Jones, Mark; Rosamond, Fran; Thomasse, Stefan; Yeo, Anders.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Published

In the parameterized problem \textsc{MaxLin2-AA}[$k$], we are given a system with variables $x_1,\ldots ,x_n$

consisting of equations of the form $\prod_{i \in I}x_i = b$, where

$x_i,b \in \{-1, 1\}$ and $I\subseteq [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 \textsc{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 \textsc{Max-$r$-Lin2-AA}[$k,r$] is the same as \textsc{MaxLin2-AA}[$k$] with two differences:

each equation has at most $r$ variables and $r$ is the second parameter. We prove a theorem on

\textsc{Max-$r$-Lin2-AA}[$k,r$]

which implies that \textsc{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:\ \{-1,1\}^n \rightarrow \mathbb{R}$ 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{\H o}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.

consisting of equations of the form $\prod_{i \in I}x_i = b$, where

$x_i,b \in \{-1, 1\}$ and $I\subseteq [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 \textsc{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 \textsc{Max-$r$-Lin2-AA}[$k,r$] is the same as \textsc{MaxLin2-AA}[$k$] with two differences:

each equation has at most $r$ variables and $r$ is the second parameter. We prove a theorem on

\textsc{Max-$r$-Lin2-AA}[$k,r$]

which implies that \textsc{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:\ \{-1,1\}^n \rightarrow \mathbb{R}$ 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{\H o}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.

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

Title of host publication | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |

Pages | 229--240 |

Publication status | Published - 2011 |

Name | LIPICS - Leibniz International Proceedings in Informatics |
---|---|

Volume | 13 |

ID: 4731424