Open access
Date
2019Type
- Conference Paper
Abstract
A function f:[n_1] x ... x[n_d]->F_2 is a direct sum if it is of the form f (a_1,...,a_d) = f_1(a_1) oplus ... oplus f_d (a_d), for some d functions f_i:[n_i]->F_2 for all i=1,..., d, and where n_1,...,n_d in N. We present a 4-query test which distinguishes between direct sums and functions that are far from them. The test relies on the BLR linearity test (Blum, Luby, Rubinfeld, 1993) and on the direct product test constructed by Dinur & Steurer (2014). We also present a different test, which queries the function (d+1) times, but is easier to analyze. In multiplicative +/- 1 notation, this reads as follows. A d-dimensional tensor with +/- 1 entries is called a tensor product if it is a tensor product of d vectors with +/- 1 entries, or equivalently, if it is of rank 1. The presented tests can be read as tests for distinguishing between tensor products and tensors that are far from being tensor products. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000370195Publication status
publishedExternal links
Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
Property testing; Direct sum; Tensor productOrganisational unit
08802 - Iozzi, Alessandra (Tit.-Prof.)
08802 - Iozzi, Alessandra (Tit.-Prof.)
More
Show all metadata