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

DOI10.4230/LIPIcs.FSTTCS.2011.229zbMath1246.68129OpenAlexW2964120731MaRDI QIDQ2911627

No author found.

Publication date: 31 August 2012

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2011.229

zbMATH Keywords

fixed-parameter tractabilitykernelizationpseudo-Boolean functionsmaxlin

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach, Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\), Maximum balanced subgraph problem parameterized above lower bound, Parameterized complexity of MaxSat above average, Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound, \textsc{Max-Cut} parameterized above the Edwards-Erdős bound, Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width, Large Independent Sets in Subquartic Planar Graphs, Hypergraph cuts above the average