Direct Sum Testing
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar · 2015
The k-fold direct sum encoding of a string α ∈ --0,1}n is a function fα that takes as input sets S ⊆ [n] of size k and outputs fα (S) = ∑i ∈ S αi (mod 2. 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 ε being a direct sum encoding.