Parallel Algorithms for Solving Sparse Binary Subset Sums Using Random Mappings

In this article we consider using random mappings to solve sparse binary subset sums via collision search. A mapping is constructed that suits our purpose and two parallel algorithms are proposed based on known collision-finding techniques. Following the applicability of binary subset sums, results of this paper are relevant to learning parities with noise, decoding random codes and related problems.