文章基本信息

标题：On Multilinear Forms: Bias, Correlation, and Tensor Rank
本地全文：下载
作者：Abhishek Bhrushundi ; Prahladh Harsha ; Pooya Hatami 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：29:1-29:23
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.29
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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â,f) : = â^'_{(iâ,, iâ,,, iâ,f) â^^ [k]Â³} T(iâ,, iâ,,, iâ,f)â<. X_{1,iâ,}â<. X_{2,iâ,,}â<. X_{3,iâ,f} 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.
关键词：polynomials; Boolean functions; tensor rank; bias; correlation