Given a system of linear equations Ax = b over the binary field F 2 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, 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.