Name
Abstract | ||
|---|---|---|
In this paper, 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 $GF(2)= {0,1}$. We show the following results for multilinear forms and tensors. 1. Correlation bounds : We show that a random $d$-linear form has exponentially low correlation with low-degree polynomials. More precisely, for $d ll 2^{o(k)}$, we show that a random $d$-linear form $f(X_1,X_2, dots, X_d) : left(GF(2)^{k}right)^d rightarrow GF(2)$ has correlation $2^{-k(1-o(1))}$ with any polynomial of degree at most $d/10$. This result is proved by giving near-optimal bounds on the bias of random $d$-linear form, which is turn proved by giving near-optimal bounds on the probability that a random rank-$t$ $d$-linear form is identically zero. 2. Tensor-rank vs Bias : We show that if a $d$-dimensional tensor has small rank, then the bias of the associated $d$-linear form is large. More precisely, given any $d$-dimensional tensor $$T :underbrace{[k]times ldots [k]}_{text{$d$ times}}to GF(2)$$ of rank at most $t$, the bias of the associated $d$-linear form $$f_T(X_1,ldots,X_d) := sum_{(i_1,dots,i_d) in [k]^d} T(i_1,i_2,ldots, i_d) X_{1,i_1}cdot X_{1,i_2}cdots X_{d,i_d}$$ is at least $left(1-frac1{2^{d-1}}right)^t$. The above bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds for $d=3$. In particular, we use this approach to prove that the finite field multiplication tensor has tensor rank at least $3.52 k$ matching the best known lower bound for any explicit tensor three dimensions over $GF(2)$. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.APPROX/RANDOM.2020.29 | Electronic Colloquium on Computational Complexity (ECCC) |
DocType | Volume | Citations |
Journal | 25 | 0 |
PageRank | References | Authors |
0.34 | 5 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhishek Bhrushundi | 1 | 5 | 2.49 |
| Prahladh Harsha | 2 | 371 | 32.06 |
| Pooya Hatami | 3 | 94 | 14.40 |
| Swastik Kopparty | 4 | 384 | 32.89 |
| Mrinal Kumar 0001 | 5 | 64 | 9.94 |