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 (10)

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

This page was built for publication: Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average