ECCC-Report TR14-002https://eccc.weizmann.ac.il/report/2014/002Comments and Revisions published for TR14-002en-usWed, 20 Jun 2018 12:49:43 +0300
Revision 1
| Direct Sum Testing |
Irit Dinur,
Roee David,
Elazar Goldenberg,
Igor Shinkar,
Guy Kindler
https://eccc.weizmann.ac.il/report/2014/002#revision1For 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.
Wed, 20 Jun 2018 12:49:43 +0300https://eccc.weizmann.ac.il/report/2014/002#revision1
Paper TR14-002
| Direct Sum Testing |
Irit Dinur,
Roee David,
Elazar Goldenberg,
Igor Shinkar,
Guy Kindler
https://eccc.weizmann.ac.il/report/2014/002For 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.
Wed, 08 Jan 2014 16:00:00 +0200https://eccc.weizmann.ac.il/report/2014/002