My view of this work is as addressing the question of testing linearity over a partial domain, which is not a linear subspace: The standard question of testing linearity refers to testing a homomorphism between two groups, but the archetypical case is when the first group is a vector space over the two-element field (and the second group is that field). The current work studies testing linearity over a non-linear subset of the vector space, specifically, the set of all vectors of fixed weight. The work contains several highly appealing results about this type of question.
For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$. In this paper we are interested in the Direct Sum Testing Problem, where we are given a function $f$, and our goal is to test whether $f$ is close to a direct sum encoding, i.e., whether there exists some $a \in \{0,1\}^n$ such that $f(S) = \sum_{i \in S} a_i$ for most inputs $S$. By identifying the subsets of $[n]$ with vectors in $\{0,1\}^n$ in the natural way, this problem can be thought of as linearity testing of functions whose domain is restricted to the $k$'th layer of the hypercube.
We first consider the case $k=n/2$, and analyze for it a variant of the natural 3-query linearity test introduced by Blum, Luby, and Rubinfeld (STOC '90). Our analysis proceeds via a new proof for linearity testing on the hypercube, which extends also to our setting.
We then reduce the Direct Sum Testing Problem for general $k < n/2$ to the case $k = n/2$, and use a recent result on Direct Product Testing of Dinur and Steurer in order to analyze the test.
See ECCC TR14-002