2 papers
cs.CC2018
On Multilinear Forms: Bias, Correlation, and Tensor Rank
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami +2
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 $G…
cs.CC2018
Torus polynomials: an algebraic approach to ACC lower bounds
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett +1
We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based app…