Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

On Multilinear Forms: Bias, Correlation, and Tensor Rank

Abhishek Bhrushundi (Rutgers)

Location:  CoRE 301
Date & time: Wednesday, 18 September 2019 at 11:00AM - 12:00PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.