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 dlinear form has exponentially low correlation with lowdegree polynomials. More precisely, for d = 2^{o(k)}, we show that a random dlinear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{k(1o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving nearoptimal bounds on the bias of a random dlinear form, which is in turn proved by giving nearoptimal bounds on the probability that a sum of t random ddimensional rank1 tensors is identically zero.
Tensor rank vs Bias. We show that if a 3dimensional tensor has small rank then its bias, when viewed as a 3linear form, is large. More precisely, given any 3dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3linear 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 tensorrank connection suggests a natural approach to proving nontrivial tensorrank 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 ddimensional 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:129:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12632},
URN = {urn:nbn:de:0030drops126325},
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 