License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.29
URN: urn:nbn:de:0030-drops-126325
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12632/
Bhrushundi, Abhishek ;
Harsha, Prahladh ;
Hatami, Pooya ;
Kopparty, Swastik ;
Kumar, Mrinal
On Multilinear Forms: Bias, Correlation, and Tensor Rank
Abstract
In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors.
Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero.
Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d.
BibTeX - Entry
@InProceedings{bhrushundi_et_al:LIPIcs:2020:12632,
author = {Abhishek Bhrushundi and Prahladh Harsha and Pooya Hatami and Swastik Kopparty and Mrinal Kumar},
title = {{On Multilinear Forms: Bias, Correlation, and Tensor Rank}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {29:1--29:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12632},
URN = {urn:nbn:de:0030-drops-126325},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.29},
annote = {Keywords: polynomials, Boolean functions, tensor rank, bias, correlation}
}
|
Keywords: |
|
polynomials, Boolean functions, tensor rank, bias, correlation |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.08.2020 |
