DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.14

A Weak Regularity Lemma for Polynomials

Authors: Guy Moshkovitz and Dora Woodruff

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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.

Cite as

Guy Moshkovitz and Dora Woodruff. A Weak Regularity Lemma for Polynomials. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{moshkovitz_et_al:LIPIcs.CCC.2026.14,
  author =	{Moshkovitz, Guy and Woodruff, Dora},
  title =	{{A Weak Regularity Lemma for Polynomials}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.14},
  URN =		{urn:nbn:de:0030-drops-270569},
  doi =		{10.4230/LIPIcs.CCC.2026.14},
  annote =	{Keywords: weak regularity lemma, finite-field polynomials, polynomial maps, structure-versus-randomness, arithmetic circuits}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.90

Slice Rank and Partition Rank of the Determinant

Authors: Amichai Lampert and Guy Moshkovitz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

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.

Cite as

Amichai Lampert and Guy Moshkovitz. Slice Rank and Partition Rank of the Determinant. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 90:1-90:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lampert_et_al:LIPIcs.ITCS.2026.90,
  author =	{Lampert, Amichai and Moshkovitz, Guy},
  title =	{{Slice Rank and Partition Rank of the Determinant}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{90:1--90:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.90},
  URN =		{urn:nbn:de:0030-drops-253779},
  doi =		{10.4230/LIPIcs.ITCS.2026.90},
  annote =	{Keywords: Slice rank, partition rank, determinant}
}

Document

DOI: 10.4230/LIPIcs.CCC.2020.35

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Authors: Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract

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.

Cite as

Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric Rank of Tensors and Subrank of Matrix Multiplication. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kopparty_et_al:LIPIcs.CCC.2020.35,
  author =	{Kopparty, Swastik and Moshkovitz, Guy and Zuiddam, Jeroen},
  title =	{{Geometric Rank of Tensors and Subrank of Matrix Multiplication}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{35:1--35:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.35},
  URN =		{urn:nbn:de:0030-drops-125874},
  doi =		{10.4230/LIPIcs.CCC.2020.35},
  annote =	{Keywords: Algebraic complexity theory, Extremal combinatorics, Tensors, Bias, Analytic rank, Algebraic geometry, Matrix multiplication}
}

Search Results

Documents authored by Moshkovitz, Guy

A Weak Regularity Lemma for Polynomials

Abstract

Cite as

Slice Rank and Partition Rank of the Determinant

Abstract

Cite as

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Abstract

Cite as

Thanks for your feedback!

Could not send message