Solving linear equations parameterized by Hamming weight

DOI10.1007/S00453-015-0098-3MaRDI QIDQ309792zbMATH OpenOpenAlexFDO

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

Publication date 7 September 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0098-3

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

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559526 (Why is no real title available?)
• A Deterministic Reduction for the Gap Minimum Distance Problem
• Color-coding
• Fundamentals of parameterized complexity
• Matching is as easy as matrix inversion
• New problems complete for nondeterministic log space
• On problems without polynomial kernels
• On the complexity of some coding problems (Corresp.)
• On the inherent intractability of certain coding problems (Corresp.)
• Parameterized complexity of constraint satisfaction problems
• Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
• Structure and importance of logspace-MOD class
• The NP-completeness column: An ongoing guide
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• The complexity of restricted spanning tree problems
• The intractability of computing the minimum distance of a code
• Undirected connectivity in log-space

Cited in

(3)

• Parameterized complexity of sparse linear complementarity problems
• Parameterized complexity of small weight automorphisms and isomorphisms
• Solving linear equations parameterized by Hamming weight

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 Q309792)