A weak regularity lemma for polynomials

Dora Woodruff; Guy Moshkovitz

REVIEW 2 major objections 5 minor 30 references

A weak regularity lemma for polynomials

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that every polynomial map over a finite field of characteristic larger than its degree has a weak regularity decomposition of polynomial size, replacing tower-type bounds, and uses it to bound generalized rank and…

desk verdict A genuinely new weak regularity lemma with attractive applications, but the main proof has a repairable gap in the choice of t that must be fixed before the results are trustworthy. read the letter →

arxiv 2509.21536 v4 pith:OLKS3JIL submitted 2025-09-25 math.CO cs.CCmath.AC

Guy Moshkovitz , Dora Woodruff This is my paper · ORCID

classification math.COcs.CCmath.AC MSC 11T06

keywords weakregularitylemmapolynomialrankfinitefieldsstructureversusrandomnessarithmeticcircuitsdepth-4formulasunivariatedegreemaps

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Standard regularity lemmas for polynomials decompose any low-degree polynomial into a bounded number of approximately independent pieces, but the number of pieces grows like a tower of exponentials. This paper proves a weaker regularity lemma whose size is polynomial in the number $m$ of input polynomials: for degree at most $d$, characteristic bigger than $d$, and error $\epsilon=q^{-r}$, the decomposition has size at most $(2m(r+1))^{2^{d(1+o(1))}}$. The weaker notion only asks that one polynomial of maximal degree behaves approximately like a free variable, independent of the others, and that is enough to see curves contained in the image of a polynomial map, which standard rank methods miss. From this the paper derives quantitative bounds on generalized polynomial rank and on the top fan-in of depth-4 arithmetic formulas, as well as a power-saving upper bound on arithmetic circuit size for maps whose image avoids low-degree curves.

What carries the argument

The carrying mechanism is the rank-regularity lemma (Theorem 2.5), which produces a minimal decomposition $P\subseteq\mathbb{F}[Y]$ in which every linear combination of the forms $Y_i$ lying outside a fixed strict subspace $U$ of their span has rank at least $t|Y|$. This is a high-rank pencil: the relevant set is $V\setminus U$ rather than the full nonzero span $V\setminus\{0\}$, and that relaxation is what avoids tower-type bounds. The lemma iteratively replaces low-rank subspaces by quadratic forms in lower-degree forms, giving size at most $((2t+1)dm)^{2^d}$. To convert this rank information into probabilities, the proof invokes Theorem 2.10, a structure-versus-randomness theorem asserting that for $\operatorname{char}(\mathbb{F})>d$, $\operatorname{rk}(P)\ge r$ implies $|\operatorname{bias}(P)|\le |\mathbb{F}|^{-c_d r/L_{\mathbb{F}}(r)}$ with $c_d=2^{-d^{1+o(1)}}$; then Lemma 2.11 shows, by an additive-character expansion, that if every linear combination outside $U$ has bias at most $\epsilon q^{-k}$, any basis of $V$ containing a basis of $U$ is weak $\epsilon$-regular. For the applications, Lemma 3.10 and a zero-set counting argument turn weak regularity into the existence of a low-degree curve inside the image of $P$, which is exactly what bounds the generalized rank and the fan-in parameters.

What would settle it

The paper's bounds could be falsified by an explicit family of degree-$d$ forms over finite fields $\mathbb{F}_q$ with $\operatorname{char}(\mathbb{F}_q)>d$ and $\operatorname{rk}(P)\ge r$ but $|\operatorname{bias}(P)|>q^{-c_d r/L_{\mathbb{F}_q}(r)}$ for $c_d=2^{-d^{1+o(1)}}$; computing the bias of, say, high-rank trilinear forms over moderately sized prime fields would locate such a counterexample if it exists. Alternatively, a polynomial map whose image avoids lines yet has $\operatorname{rk}_{d/2}(P)$ exceeding $(2m)^{2^{d(1+o(1))}}$ would disprove the main rank application.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the usual regularity-lemma requirement, that all nontrivial linear combinations of the decomposition parts have high rank, can be relaxed without losing utility. The new weak regularity lemma (Theorem 2.2) states that for any finite field $\mathbb{F}$ with $d<\operatorname{char}(\mathbb{F})$, every $m$-tuple $P$ of degree-at-most-$d$ polynomials has a weak $\epsilon$-regular decomposition of size at most $(2m(r+1))^{2^{d(1+o(1))}}$ when $\epsilon=q^{-r}$. In such a decomposition $P=F(X_1,\ldots,X_k)$ with the $X_i$ homogeneous, the first part $X_1$ has maximal degree, $P$ genuinely depends on $X_1$, and conditioned on the other parts taking any fixed value, $X_1$ is distributed almost uniformly over $\mathbb{F}$. The proof reaches this through a rank-regularity lemma for high-rank pencils, a structure-versus-randomness theorem that converts rank into bias, and a character-sum computation that converts bias into weak regularity. The same machinery yields the quantitative rank bound $\operatorname{rk}_{d/u}(P)\le (2m)^{2^{d(1+o(1))}}$ for $u=\operatorname{udeg}(P)$, and the corresponding depth-4 formula bound.

Load-bearing premise

The load-bearing premise is an imported structure-versus-randomness theorem, not proved in this paper, claiming that over a finite field of characteristic greater than the degree, a polynomial of large rank must have correspondingly tiny bias; if that theorem were false or materially weaker, the polynomial-size regularity bounds would not follow.

Editorial extensions

If this is right

Every degree-$d$ polynomial map over a finite field of characteristic greater than $d$ has a weak $\epsilon$-regular decomposition whose size is polynomial in the number $m$ of polynomials, rather than a tower in $d$ and $m$.
If the image of such a map contains no line, then its $d/2$-rank is at most $(2m)^{2^{d(1+o(1))}}$, independent of the number of variables and of the field size.
For $u=\operatorname{udeg}(P)$, the $d/u$-rank of any polynomial map $P$ is bounded by the same quantity, making the earlier qualitative generalized-rank bound quantitative and extending it to tuples of polynomials.
Any polynomial generated by an $m$-tuple of degree-at-most-$d$ polynomials with univariate degree at least $u$ is computable by a depth-4 formula with bottom fan-in at most $d/u$, top fan-in at most $(2m)^{2^{d(1+o(1))}}$, and at most $2u$ factors in each product.
A map whose image avoids curves of degree below $u$ is computable by an arithmetic circuit of size $n^{\lfloor d/u\rfloor+o(1)}$, so strong lower bounds for such maps would have to evade this power-saving upper bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the size bound is polynomial in $m$ but double-exponential in $d$, the method is most naturally useful in the low-degree regime $d=O(1)$; for large $d$ the constants would dominate.
Any improvement to the imported structure-versus-randomness constant $c_d$ would transfer directly to the weak regularity lemma, so the double-exponential dependence on $d$ is not intrinsic to the combinatorial part of the argument.
The image-avoidance condition offers a testable geometric handle: one could inspect zero sets or fibers of explicit polynomial maps to see where the $d/u$-rank bound is tight.
The same weak-regularity perspective may apply to other image-based questions, such as counting points of polynomial maps or bounding intersections of images with algebraic varieties, where standard rank methods give only equidistribution information.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

You should know two things. The paper introduces a genuinely new weak regularity lemma for polynomials, with decomposition size polynomial in the number of polynomials m—roughly (2m)^{2^{d(1+o(1))}}—and the applications to rank bounds and depth-4 top fan-in are new. But there is a real gap in the proof of the central lemma, Theorem 2.2. The stress-test note is correct: the asserted choice of t is too small by a factor exponential in d. At the maximal k, the inequality q^{-c_d t k/L_F(tk)} < q^{-r-k} fails because L_F(tS) is about 2^d(log t + log m), while c_d t is only (r+1)^{1+o(1)} log m, giving a ratio of roughly 2^{-d} instead of the required ≥ 1. A larger t, about 2^{O(d)} times the stated value, restores the inequality, and the final bound (2m(r+1))^{2^{d(1+o(1))}} should survive up to the usual o(1). But as written the proof is incomplete, and this is not a typo-level issue.

When that is repaired, the paper is a solid contribution. The rank-regularity lemma (Theorem 2.5) is a nice new tool, the Fourier step isolating one free variable is elegant, and the application to curves in the image is genuinely beyond what standard rank methods give. I also think the paper is honest about its dependencies: the MZ24 theorem is not proved here, but the authors note that Janzer's or Milicevic's bounds can be substituted at the cost of weaker constants, so that reliance is not load-bearing. The mechanical problems the reader flagged—duplicate [LZ24], the exponent typo in the intro, and the U/U_i notation clash in Theorem 3.7—are real but easily fixed.

My bottom line: this deserves a serious referee, but the referee should be told to focus on the choice of t in Theorem 2.2 and on whether the final bound survives a correct choice. I would not cite it as-is, and I would not bring it to a reading group until the gap is sorted. If the authors fix the proof, this becomes a genuinely useful paper for additive combinatorics and algebraic complexity.

Best.

Referee Report

2 major / 5 minor

Summary. The paper defines a weak regularity lemma for polynomial tuples over finite fields: every m-tuple of degree-d polynomials over F_q with d<char(F) is shown to have a decomposition into homogeneous polynomials X_1,...,X_k, with k polynomial in m, such that the top-degree part is approximately uniform even after conditioning on the others. The main theorem claims a size bound k ≤ (2m(r+1))^{2^{d(1+o(1))}} for approximation parameter ε=q^{-r}. The proof proceeds through a rank-regularity lemma for polynomial pencils, a bias bound from Moshkovitz–Zhu, Fourier analysis to convert low bias into weak regularity, and then applications to curves in the image of polynomial maps. The applications include a quantitative bound for Karam's generalized rank rk_{d/u}(P) in terms of the univariate degree u=udeg(P), a rank_{d/2} bound when the image contains no line, and depth-4 formulas with bounded top fan-in.

Significance. If the proof gap discussed below is repaired, the paper makes a substantial contribution: it replaces tower-type or non-explicit bounds in polynomial regularity lemmas with an explicit polynomial-in-m bound, and it shows that this weak form of regularity is strong enough for image and curve questions that standard rank methods cannot address. The applications to Karam's rank problem and to top fan-in of depth-4 formulas are concrete and new. The notion of univariate degree of a polynomial map is natural and well motivated. The proof is mostly self-contained after Theorem 2.10, the reductions are clean, and no parameters are fitted to make the final bounds work; the paper is also explicit that its central bias step relies on the MZ24 theorem.

major comments (2)

[Section 2.3, proof of Theorem 2.2] The choice of t does not satisfy the displayed bias inequality. The proof requires that for every k ≤ S := ((2t+1)dm)^{2^d} we have q^{-c_d t k / L_F(tk)} < q^{-r} q^{-k}, equivalently c_d t / L_F(tk) > (r/k)+1. With the stated t = 2^{d^{1+o(1)}} (r+1)^{1+o(1)} log m, the condition already fails at k=1: the left-hand side is about (r+1)^{1+o(1)} log m divided by log_q(t)+1 ≈ d^{1+o(1)}, which tends to 0 in d for bounded m,r; when m=1 the formula gives t=0. At k=S the failure is even more transparent: L_F(tS) is on the order of 2^d(log_q t + log_q m), so c_d t / L_F(tS) is roughly 2^{-d} times the same ratio, again well below the required value 1+r/S. Thus the main lemma is not proved as written. This is fixable by taking t about 2^d c_d^{-1} times a logarithmic factor in t and m, and the extra 2^d is plausibly absorbed in the final 2^{d(1+o(1))} exponent, but the displayed derivation must be corrected.
[Section 2.2, Theorem 2.10] The proof of Theorem 2.2 is fully dependent on the bias bound of Moshkovitz–Zhu, which is cited as an unpublished submitted paper and is coauthored by the first author. This theorem is load-bearing: the rank-regularity lemma gives rank, and Theorem 2.10 is the only bridge from rank to the bias values needed in Lemma 2.11. The manuscript should either include a proof of Theorem 2.10 or cite a published/accepted version. Moreover, the corrected choice of t in the previous comment depends on the exact value c_d = 2^{-d^{1+o(1)}}; if the constant in [MZ24] has a different dependence on d, the final bound in Theorem 2.2 needs to be rechecked.

minor comments (5)

[Abstract and Section 1.2] The abstract promises an arithmetic circuit size bound n^{⌊d/u⌋+o(1)} for polynomial maps whose image avoids curves of degree below u, but the body (Theorem 1.2) only states a depth-4 formula with top fan-in r ≤ (2m)^{2^{d(1+o(1))}} and bottom fan-in at most d/u. The circuit-size implication is not derived in the text; please add the derivation or revise the abstract.
[Section 2.3 and Section 3.2] The applications in Theorem 3.7 set ε = 1-d/q. In the boundary case d = q-1 this equals q^{-1}, i.e. r=1, while the introduction states Theorem 2.2 for ε=q^{-r} with r>1. Please clarify whether Theorem 2.2 is intended for all r>0, and adjust the statements accordingly.
[Section 2.1.2, proof of Theorem 2.5] The displayed induction bound on r_i has an exponent that appears to be 2^i-1; with i=0 this would be negative and incompatible with the base case r_0 ≤ dm. The indexing should be cleaned up.
[Section 3.1, Proposition 3.9] Proposition 3.9 item 2 states udeg(P)<|F|, but Definition 3.5 sets udeg(P)=∞ for constant P. Please exclude the constant case there or adjust the statement.
[Introduction] There are minor typographical issues, including 'the the finite-field Gowers inverse conjecture' in Section 1 and the duplicate reference [LZ24] with different titles in the bibliography.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the weak regularity lemma is proved from self-contained rank-regularity arguments plus a parameter-free cited bias theorem whose hypotheses do not include the target results.

full rationale

The paper's derivation chain is not circular. The central object, the weak regularity lemma (Theorem 2.2), is proved by combining the rank-regularity lemma (Theorem 2.5), which is proved in full in Section 2.1, with a Fourier-analytic conversion Lemma 2.11 and the cited structure-vs-randomness theorem (Theorem 2.10). Theorem 2.10 is the only ingredient authored by a current author ([MZ24], G. Moshkovitz and D. Zhu), and although it is logically load-bearing, it is an independent parameter-free statement: for char(F)>d, high rank forces small bias. Its assumptions do not mention weak regularity, decomposition size, univariate degree, or the rank bounds that this paper claims; it is not equivalent to any output of the paper by construction. Under the review rules, such a citation is real evidence and does not raise the circularity score. The applications in Section 3 (Theorems 3.3, 3.7, and 1.2) follow from the proved weak regularity lemma plus lemmas proved in the paper (Lemmas 3.10, 3.11, 3.12, and Corollary 3.13), with no fitted parameters renamed as predictions. A separate concern that the choice of t in the proof of Theorem 2.2 may be too small by an exponential-in-d factor is a potential correctness gap in the written proof, not a circularity: it does not make the conclusion an input of the argument. No equation is defined in terms of another target equation, and no uniqueness or ansatz is imported from the authors' prior work to force the conclusion.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted; all bounds are explicit. The central new content is a proof that relies on one substantial external theorem (MZ24) plus standard finite-field background. No new physical or algebraic entities are postulated beyond definitions such as univariate degree, which is a measure rather than an introduced object.

assumptions (3)

domain assumption Structure-vs-randomness theorem (MZ24, Theorem 2.10): for char(F)>d, rk(P)>=r implies |bias(P)| <= |F|^{-c_d r/L_F(r)} with c_d = 2^{-d^{1+o(1)}}.
Load-bearing external theorem used in the proof of Theorem 2.2 to convert t-rank-regularity into low bias; not proved in this paper and authored by coauthor Moshkovitz.
standard math Finite-field polynomial function algebra: polynomials are identified with functions via unique reduced representation, and total degree, supports, and bias are well-defined; the Schwartz-Zippel lemma holds.
Background used throughout Sections 1.5, 2.2, and 3.2.
domain assumption The restriction d < char(F) is in force in all main theorems.
Required for the rank-bias theorem and for degree and rank arguments; excludes small characteristic. Stated explicitly in the main results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A weak regularity lemma for polynomials." pith.science (2026). https://pith.science/paper/OLKS3JIL

@misc{pith2026250921536,
  author       = {Pith},
  title        = {Pith review of: A weak regularity lemma for polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OLKS3JIL}},
  note         = {Machine review of arXiv:2509.21536}
}

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 tools for quantitatively studying the curves contained in the image of a polynomial map, which is beyond the reach of standard rank 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 polynomial maps based solely on their image: if the image avoids curves of degree below $u$ then there is an arithmetic circuit of size $n^{\lfloor d/u \rfloor + o(1)}$, a power-saving bound compared to the typical $n^{d-o(1)}$ bound for degree-$d$ polynomials. - 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

[1]

Ananyan and M

T. Ananyan and M. Hochster, Small subalgebras of polynomial rings and Stillman's Conjecture , J. Amer. Math. Soc. 33 (2020), 291--309

work page 2020
[2]

Bhowmick and S

A. Bhowmick and S. Lovett, Bias vs structure of polynomials in large fields, and applications in information theory , IEEE Trans. Inf. Theory 69 (2023), 963--977

work page 2023
[3]

Bogdanov and E

A. Bogdanov and E. Viola, Pseudorandom bits for polynomials , SIAM J. Comput. 39 (2010), 2464--2486

work page 2010
[4]

Cohen and G

A. Cohen and G. Moshkovitz, Partition and analytic rank are equivalent over large fields , Duke Math. J. 172 (2023), 2433--2470

work page 2023
[5]

Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits

P. Dutta, P. Dwivedi, and N. Saxena, Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits , 36th Computational Complexity Conference (CCC 2021), 1--27, arXiv:2304.11325 https://arxiv.org/abs/2304.11325 (2023)

work page Pith review arXiv 2023
[6]

Erman, S

D. Erman, S. V. Sam, and A. Snowden, Cubics in 10 variables vs. cubics in 1000 variables: uniformity phenomena for bounded degree polynomials , Bull. Amer. Math. Soc. 56 (2019), 87--114

work page 2019
[7]

Frieze and R

A. Frieze and R. Kannan, Quick approximation to matrices and applications , Combinatorica 19 (1999), 175--220

work page 1999
[8]

W. T. Gowers and J. Wolf, Linear forms and higher-degree uniformity for functions on F ^n_p , Geom. Funct. Anal. 21 (2011), 36--69

work page 2011

Show all 30 references

[9]

Green, Montreal lecture notes on quadratic Fourier analysis , Additive Combinatorics (Montr\' e al 2006, ed

B. Green, Montreal lecture notes on quadratic Fourier analysis , Additive Combinatorics (Montr\' e al 2006, ed. Granville et al.), CRM Proceedings 43, AMS 2007, 69--102. arXiv:0604089 https://arxiv.org/abs/math/0604089

2006 arXiv
[10]

Green and T

B. Green and T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms , Contrib. Discrete Math. 4 (2009), 1--36

2009
[11]

Gutierrez, R

J. Gutierrez, R. Rubio and D. Sevilla, On multivariate rational function decomposition , J. Symb. Comput. 33 (2002), 545--562

2002
[12]

Hatami and S

H. Hatami and S. Lovett, Higher-order Fourier analysis of F _p^n and the complexity of systems of linear forms , Geom. Funct. Anal. 21, (2011), 1331--1357

2011
[13]

Hou, Permutation polynomials over finite fields — A survey of recent advances , Finite Fields Their Appl

X. Hou, Permutation polynomials over finite fields — A survey of recent advances , Finite Fields Their Appl. 32 (2015), 82--119

2015
[14]

Janzer, Polynomial bound for the partition rank vs the analytic rank of tensors , Discrete Anal

O. Janzer, Polynomial bound for the partition rank vs the analytic rank of tensors , Discrete Anal. 7 (2020)

2020
[15]

Karam, Ranges of polynomials control degree ranks of Green and Tao over finite prime fields , arXiv:2305.11088 https://arxiv.org/abs/2305.11088 (2023)

T. Karam, Ranges of polynomials control degree ranks of Green and Tao over finite prime fields , arXiv:2305.11088 https://arxiv.org/abs/2305.11088 (2023)

2023
[16]

Kaufman and S

T. Kaufman and S. Lovett, Worst case to average case reductions for polynomials , 42th IEEE Symposium on Foundations of Computer Science (FOCS 2008) , 166--175

2008
[17]

Kaufman, S

T. Kaufman, S. Lovett and E. Porat, Weight distribution and list-decoding size of Reed–Muller codes , IEEE Trans. Inf. Theory , 58 (2012), 2689--2696

2012
[18]

Kayal, C

N. Kayal, C. Saha, and R. Saptharishi, A super-polynomial lower bound for regular arithmetic formulas , 46th ACM Symposium on Theory of Computing (STOC 2014) , 146--153

2014
[19]

Kazhdan, A

D. Kazhdan, A. Lampert, and A. Polishchuk, Schmidt rank and singularities , Ukr. Math. J. 75 (2024), 1420--1442

2024
[20]

Kumar and S

M. Kumar and S. Saraf, The limits of depth reduction for arithmetic formulas: it's all about the top fan-in , 46th ACM Symposium on Theory of Computing (STOC 2014) , 136--145

2014
[21]

Lampert, Small ideals in polynomial rings and applications , arXiv:2309.16847 https://arxiv.org/abs/arXiv:2309.16847 (2023)

A. Lampert, Small ideals in polynomial rings and applications , arXiv:2309.16847 https://arxiv.org/abs/arXiv:2309.16847 (2023)

2023 arXiv
[22]

Lampert and T

A. Lampert and T. Ziegler, On rank in algebraic closure , arXiv:2205.05329 https://arxiv.org/abs/arXiv:2205.05329 (2022)

2022 arXiv
[23]

Lampert and T

A. Lampert and T. Ziegler, Relative rank and regularization , Forum Math. Sigma 12:e29 (2024)

2024
[24]

Mili\' c evi\' c , Polynomial bound for partition rank in terms of analytic rank , Geom

L. Mili\' c evi\' c , Polynomial bound for partition rank in terms of analytic rank , Geom. Funct. Anal. 29 (2019), 1503--1530

2019
[25]

Moshkovitz and D

G. Moshkovitz and D. Zhu , Quasi-linear relation between partition and analytic rank , arXiv:2211.05780 https://arxiv.org/abs/2211.05780 (2024), submitted

2024 arXiv
[26]

Naslund, The partition rank of a tensor and k-right corners in F ^n_q , J

E. Naslund, The partition rank of a tensor and k-right corners in F ^n_q , J. Comb. Theory Ser. A. 174 (2020), 105190

2020
[27]

Raz, Elusive functions and lower bounds for arithmetic circuits , Theory Comput

R. Raz, Elusive functions and lower bounds for arithmetic circuits , Theory Comput. 6 (2010), 135--177

2010
[28]

W. M. Schmidt, The density of integer points on homogeneous varieties , Acta Math. 154 (1985), 243--296

1985
[29]

Tao and T

T. Tao and T. Ziegler, The inverse conjecture for the Gowers norm over finite fields in low characteristic , Ann. Comb. 16 (2012), 121--188

2012
[30]

von zur Gathen and K

J. von zur Gathen and K. Ziegler, Survey on counting special types of polynomials , Computer Algebra and Polynomials, Lecture Notes in Computer Science , 8942 (2015), Springer

2015

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Ananyan and M

T. Ananyan and M. Hochster, Small subalgebras of polynomial rings and Stillman's Conjecture , J. Amer. Math. Soc. 33 (2020), 291--309

work page 2020

[2] [2]

Bhowmick and S

A. Bhowmick and S. Lovett, Bias vs structure of polynomials in large fields, and applications in information theory , IEEE Trans. Inf. Theory 69 (2023), 963--977

work page 2023

[3] [3]

Bogdanov and E

A. Bogdanov and E. Viola, Pseudorandom bits for polynomials , SIAM J. Comput. 39 (2010), 2464--2486

work page 2010

[4] [4]

Cohen and G

A. Cohen and G. Moshkovitz, Partition and analytic rank are equivalent over large fields , Duke Math. J. 172 (2023), 2433--2470

work page 2023

[5] [5]

Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits

P. Dutta, P. Dwivedi, and N. Saxena, Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits , 36th Computational Complexity Conference (CCC 2021), 1--27, arXiv:2304.11325 https://arxiv.org/abs/2304.11325 (2023)

work page Pith review arXiv 2023

[6] [6]

Erman, S

D. Erman, S. V. Sam, and A. Snowden, Cubics in 10 variables vs. cubics in 1000 variables: uniformity phenomena for bounded degree polynomials , Bull. Amer. Math. Soc. 56 (2019), 87--114

work page 2019

[7] [7]

Frieze and R

A. Frieze and R. Kannan, Quick approximation to matrices and applications , Combinatorica 19 (1999), 175--220

work page 1999

[8] [8]

W. T. Gowers and J. Wolf, Linear forms and higher-degree uniformity for functions on F ^n_p , Geom. Funct. Anal. 21 (2011), 36--69

work page 2011