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}
}

Search Results

Documents authored by Woodruff, Dora

A Weak Regularity Lemma for Polynomials

Abstract

Cite as

Thanks for your feedback!

Could not send message