*BibTeX*

@Article{AKKT16linearequations, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Jacobo Tor\'an}, title = {Solving linear equations parameterized by {Hamming} weight}, journal = {Algorithmica}, year = 2016, volume = 75, number = 2, pages = {322-338}, issn = {0178-4617}, doi = {10.1007/s00453-015-0098-3}, }

**Solving linear equations
parameterized by Hamming weight.**

With V. Arvind,
Johannes
Köbler, Jacobo Torán.

*Algorithmica* 75:2 (Jun. 2016), pp. 322–338.

Abstract.Given a system of linear equations Ax=b over the binary field and an integer t≥1, we study the following three algorithmic problems:

1. Does Ax=b have a solution of weight at most t?

2. Does Ax=b have a solution of weight exactly t?

3. Does Ax=b have a solution of weight at least t?

We investigate the parameterized complexity of these problems with t as parameter. A special aspect of our study is to show how the maximum multiplicity k of variable occurrences in Ax=b influences the complexity of the problem. We show a sharp dichotomy: for each k≥3 the first two problems are W[1]-hard (which strengthens and simplifies a result of Downey et al. [SIAM J Comput 29(2), 545–570, 1999]). For k=2, the problems turn out to be intimately connected to well-studied matching problems and can be efficiently solved using matching algorithms.

*BibTeX*

@InProceedings{AKKT14linearequations, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Jacobo Tor\'an}, title = {Solving linear equations parameterized by {Hamming} weight}, booktitle = {Parameterized and Exact Computation (Proceedings of 9th IPEC)}, year = 2014, series = {LNCS}, number = 8894, publisher = {Springer}, address = {Berlin}, isbn = {978-3-319-13523-6}, doi = {10.1007/978-3-319-13524-3_4}, pages = {39-50}, }

Conference version:

**Solving linear equations parameterized by Hamming
weight**

With V. Arvind,
Johannes
Köbler, Jacobo Torán.

*Parameterized and Exact Computation* (Proceedings of
9th IPEC).
Springer, 2014. Pp. 39-50.