Abstract
The k-fold direct sum encoding of a string α in {0,1}^n is a function fα that takes as input sets S subset of [n] of size k and outputs the sum mod 2 of α_i for i in S. In this paper we prove a Direct Sum Testing theorem.
We describe a three query test that accepts with probability one any function of the form fα for some α, and rejects with probability Ω(ε) functions f that are ε-far from being a direct sum encoding.