Direct Sum Testing

Elazar Goldenberg

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 talk we are discuss 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