Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
From MaRDI portal
Publication:2392244
DOI10.1007/s00224-012-9415-2zbMath1290.68056arXiv1110.5915OpenAlexW2095908779MaRDI QIDQ2392244
Publication date: 1 August 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.5915
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Parameterized complexity of MaxSat above average
- A probabilistic approach to problems parameterized above or below tight bounds
- Solving MAX-\(r\)-SAT above a tight lower bound
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Parameterizing above or below guaranteed values
- Almost 2-SAT is fixed-parameter tractable
- On Multiway Cut Parameterized above Lower Bounds
- Improved Parameterized Algorithms for above Average Constraint Satisfaction
- Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
- Paths, Flowers and Vertex Cover
- Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
- Algorithms with large domination ratio
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Faster Parameterized Algorithms Using Linear Programming
- Some optimal inapproximability results
This page was built for publication: Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
