Solving linear equations parameterized by Hamming weight

DOI10.1007/978-3-319-13524-3_4zbMATH Open1341.68056OpenAlexW2353983MaRDI QIDQ2946006FDOQ2946006

Authors: Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán 

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13524-3_4

Recommendations

• Solving linear equations parameterized by Hamming weight
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear equations (linear algebraic aspects) (15A06)

Cited In (6)

• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• Fixed-parameter tractability of error correction in graphical linear systems
• Solving linear equations parameterized by Hamming weight
• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Weighted counting of solutions to sparse systems of equations

This page was built for publication: Solving linear equations parameterized by Hamming weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946006)