Abstract
A tensor defined over a finite field has low analytic rank if the distribution of its values differs significantly from the uniform distribution. An order tensor has partition rank 1 if it can be written as a product of two tensors of order less than , and it has partition rank at most if it can be written as a sum of tensors of partition rank 1. In this paper, we prove that if the analytic rank of an order tensor is at most , then its partition rank is at most , where, for fixed and , is a polynomial in . This is an improvement of a recent result of the author, where he obtained a tower-type bound. Prior to our work, the best known bound was an Ackermann-type function in and , though it did not depend on . It follows from our results that a biased polynomial has low rank; there too we obtain a polynomial dependence improving the previously known Ackermann-type bound. A similar polynomial bound for the partition rank was obtained independently and simultaneously by Milićević.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.