TR14-002 Authors: Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

Publication: 8th January 2014 16:00

Downloads: 1664

Keywords:

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.