### Abstract

_{1}, . . . , x

_{n}consisting of equations of the form ∏

_{ i∈I}xi = b, where xi , b ∈ {−1, 1} and 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 + 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 : {−1, 1}

^{n}→ 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ő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 | Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |

Editors | Supratik Chakraborty, Amit Kumar |

Place of Publication | Germany |

Publisher | Dagstuhl Publishing |

Pages | 229-240 |

Number of pages | 12 |

Volume | 13 |

ISBN (Print) | 978-3-939897-34-7 |

DOIs | |

Publication status | Published - 2011 |

Event | International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2011 31st) - India, India Duration: 12 Dec 2011 → 14 Dec 2011 Conference number: 2011 (31st) |

### Conference

Conference | International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2011 31st) |
---|---|

Abbreviated title | FST&TCS |

Country | India |

Period | 12/12/11 → 14/12/11 |

### Fingerprint

### Cite this

*Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science*(Vol. 13, pp. 229-240). Germany: Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2011.i

}

*Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science.*vol. 13, Dagstuhl Publishing, Germany, pp. 229-240, International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2011 31st), India, 12/12/11. https://doi.org/10.4230/LIPIcs.FSTTCS.2011.i

**Simultaneously satisfying linear equations over F2 : MaxLin2 and Max-r-Lin2 Parameterized above average.** / Crowston, Robert; Fellows, Michael; Gutin, Gregory; Jones, Mark; Rosamond, Frances; Thomasse, Stephan; Yeo, Anders.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › Research › peer-review

TY - GEN

T1 - Simultaneously satisfying linear equations over F2

T2 - MaxLin2 and Max-r-Lin2 Parameterized above average

AU - Crowston, Robert

AU - Fellows, Michael

AU - Gutin, Gregory

AU - Jones, Mark

AU - Rosamond, Frances

AU - Thomasse, Stephan

AU - Yeo, Anders

PY - 2011

Y1 - 2011

N2 - In the parameterized problem MaxLin2-AA[k], we are given a system with variables x1, . . . , xn consisting of equations of the form ∏ i∈I xi = b, where xi , b ∈ {−1, 1} and 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 + 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 : {−1, 1} n → 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ő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.

AB - In the parameterized problem MaxLin2-AA[k], we are given a system with variables x1, . . . , xn consisting of equations of the form ∏ i∈I xi = b, where xi , b ∈ {−1, 1} and 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 + 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 : {−1, 1} n → 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ő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.

KW - Connected graph

KW - Fixed-parameter tractability

KW - Fourier expansion

KW - Kernelization

KW - Maxlin

KW - Multilinear polynomials

KW - Parameterized problems

KW - Pseudo-Boolean function

KW - Boolean functions

KW - Software engineering

KW - Theorem proving

KW - Graph theory

U2 - 10.4230/LIPIcs.FSTTCS.2011.i

DO - 10.4230/LIPIcs.FSTTCS.2011.i

M3 - Conference Paper published in Proceedings

SN - 978-3-939897-34-7

VL - 13

SP - 229

EP - 240

BT - Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

A2 - Chakraborty, Supratik

A2 - Kumar, Amit

PB - Dagstuhl Publishing

CY - Germany

ER -