Solving linear equations parameterized by Hamming weight

DOI10.1007/S00453-015-0098-3zbMATH Open1350.68124OpenAlexW2301110862MaRDI QIDQ309792FDOQ309792

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

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

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)

Cites Work

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

Cited In (2)

• Parameterized complexity of sparse linear complementarity problems
• Parameterized complexity of small weight automorphisms and isomorphisms

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)