Solving linear equations parameterized by Hamming weight

DOI10.1007/s00453-015-0098-3zbMath1350.68124OpenAlexW2301110862MaRDI QIDQ309792

V. Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran

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)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Parameterized complexity of constraint satisfaction problems
• On problems without polynomial kernels
• 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
• Undirected connectivity in log-space
• 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
• On the inherent intractability of certain coding problems (Corresp.)
• Color-coding
• The intractability of computing the minimum distance of a code
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• The NP-completeness column: An ongoing guide

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