Solving linear equations parameterized by Hamming weight

DOI10.1007/978-3-319-13524-3_4MaRDI QIDQ2946006zbMATH OpenOpenAlexFDO

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

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)

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

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)