Direct Sum Testing

by Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar

Oded's comments

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.

The original abstract

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

Back to list of Oded's choices.