Abhishek Bhrushundi, Rutgers University

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). Our first result shows that a random d-linear form has exponentially low correlation with low-degree polynomials. This result is proved by giving near-optimal bounds on the bias of random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a random rank-t d-linear form is identically zero. Our second result shows that if a d-dimensional tensor has small rank, then the bias of the associated d-linear form is large. This is joint work with Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar.