Abstract
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.
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/Territory | India |
Period | 12/12/11 → 14/12/11 |