The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>

This work investigates the hardness of computing sparse solutions to systems of linear equations over \mathbb{F}_2. Consider the k-EvenSet problem: given a homogeneous system of linear equations over \mathbb{F}_2 on n variables, decide if there exists a nonzero solution of Hamming weight at most k (i.e. a k-sparse solution). While ... more >>>