@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.

@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.