A regularity lemma for polynomials provides a decomposition in terms of a bounded number of approximately independent polynomials. Such regularity lemmas play an important role in numerous results, yet suffer from the familiar shortcoming of having tower-type bounds or worse. In this paper we design a new, weaker regularity lemma with strong bounds. The new regularity lemma in particular provides means for quantitatively studying the curves contained in the image of a polynomial map, which is beyond the reach of standard methods. The weak regularity lemma turns out to be powerful enough to yield results on arithmetic circuits and polynomial ranks that may be of independent interest: - A general upper bound on the arithmetic circuit size of low-degree polynomials based solely on their image. - An upper bound on the top fan-in of depth-4 arithmetic formulas under similar conditions. - A quantitative bound for the Green-Tao notion of rank for polynomials, significantly improving on a result of Karam.

The Laplace expansion expresses the n × n determinant det_n as a sum of n products. Do shorter expansions exist? In this paper we: - Fully determine the slice rank decompositions of det_n (where each product must contain a linear factor): In this case, we show that n summands are necessary, and moreover, the only such expansions with n summands are equivalent (in a precise sense) to the Laplace expansion. - Prove a logarithmic lower bound for the partition rank of det_n (where each product is of multilinear forms): In this case, we show that at least log₂(n)+1 summands are needed and we explain why existing techniques fail to yield any nontrivial lower bound. - Separate partition rank from slice rank for det_n: we find a quadratic expansion for det₄, over any field, with fewer summands than the Laplace expansion. This construction is related to a well-known example of Green-Tao and Lovett-Meshulam-Samorodnitsky disproving the naive version of the Gowers Inverse conjecture over small fields. An important motivation for these questions comes from the challenge of separating structure and randomness for tensors. On the one hand, we show that the random construction fails to separate: for a random tensor of partition rank r, the analytic rank is r-o(1) with high probability. On the other hand, our results imply that the determinant yields the first asymptotic separation between partition rank and analytic rank of d-tensors, with their ratio tending to infinity with d.

We prove that the slice rank of a 3-tensor (a combinatorial notion introduced by Tao in the context of the cap-set problem), the analytic rank (a Fourier-theoretic notion introduced by Gowers and Wolf), and the geometric rank (a recently introduced algebro-geometric notion) are all equivalent up to an absolute constant. As a corollary, we obtain strong trade-offs on the arithmetic complexity of a biased bililnear map, and on the separation between computing a bilinear map exactly and on average. Our result settles open questions of Haramaty and Shpilka [STOC 2010], and of Lovett [Discrete Anal., 2019] for 3-tensors.

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen's well-known lower bound from 1987.

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders. Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Two examples of our results are the following: Motivated by the Unique Games Conjecture, Trevisan [FOCS O5] and Arora, Barak and Steurer [FOCS 10] showed that given a graph G, one can remove only 1% of G's edges and thus obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are (essentially) best possible even when one is allowed to remove 99% of G's edges. In particular, our results imply that the eigenspace enumeration approach of Arora-Barak-Steurer cannot give (even quasi-) polynomial time algorithms for unique games. A classical result of Lipton, Rose and Tarjan from 1979 states that if ℱ is a hereditary family of graphs and every graph in ℱ has a vertex separator of size n/(log n)1+o(1), then every graph in ℱ has O(n) edges. We construct a hereditary family of graphs with vertex separators of size n/(log n)1–o(1) such that not all graphs in the family have O(n) edges. The above results are obtained as corollaries of a new family of graphs, which we construct by picking random subgraphs of the hypercube, and analyze using (simple) arguments from the theory of metric embedding.

We present a combinatorial approach for proving complexity lower bounds; we focus on the following instantiation of this approach. For a property of regular hypergraphs with m edges and an arbitrary hypergraph G with m - t edges, we may count the number of super-hypergraphs of G (i.e., hypergraphs obtained by adding t edges) satisfying the property. Suppose that we find a pair of these properties where every such G has the same number of super-hypergraphs satisfying each property. We show that in this case, we immediately obtain an explicit m/(t - 1) lower bound on the rank of tensors (which are high-dimensional matrices). Notice that if the hypergraphs are 3-uniform, this implies a lower bound of Ω(m/t) for arithmetic circuits. We also show, albeit non-explicitly, that essentially-optimal lower bounds can be obtained using this approach. Furthermore, we exemplify our approach in the t = 2 case, and prove that even in this case we can already obtain interesting lower bounds. In particular, we derive a (tight) lower bound of 3n/2 on the rank of n × n × n tensors that are naturally associated with hypergraph trees. In fact, our bound also applies to the stronger notion of border rank, for which our result essentially matches the best lower bounds known.