Pith. sign in

REVIEW 3 major objections 5 minor 34 references

Closure under factorization from a result of Furstenberg

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Constant-depth algebraic circuits and algebraic formulas are closed under taking factors.

desk verdict Solves the closure-under-factors problem for formulas and constant-depth circuits with a genuinely novel proof; the main risk is a gap in how the Andrews-Wigderson theorem is applied in Theorem 4.3, but it's fixable. read the letter →

arxiv 2506.23214 v1 pith:AGSSWUCY submitted 2025-06-29 cs.CC

Somnath Bhattacharjee , Mrinal Kumar , Shanthanu S. Rai , Varun Ramanathan , Ramprasad Saptharishi , Shubhangi Saraf This is my paper · ORCID
classification cs.CC MSC 68Q1512D0513P05
keywords algebraiccircuitspolynomialfactorizationconstant-depthformulaspowerseriesrootsdiagonaloperatoridentitytestinghardness-randomnesstrade-offs
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

This paper aims to settle a long-standing closure question: if a multivariate polynomial is computed by a small algebraic formula or a small constant-depth algebraic circuit, are all of its factors computed in the same model? The answer, over fields of characteristic zero (and sufficiently large characteristic), is yes. For a degree-$d$ polynomial on $n$ variables computed by a size-$s$ depth-$\Delta$ circuit, every factor is computed by a circuit of size $\mathrm{poly}(s,d,n)$ and depth $\Delta+O(1)$; for a size-$s$ formula, every factor is computed by a formula of size $\mathrm{poly}(s,d,n)$. The proof is driven by a 1960s identity that gives a non-iterative, closed-form expression for power-series roots of a bivariate polynomial, turning a sequential lifting process into one finite formula whose truncations inherit constant depth and polynomial size.

What carries the argument

The load-bearing object is the diagonal operator on bivariate power series, $D(\sum_{i,j} F_{i,j}t^i y^j)=\sum_i F_{i,i}t^i$, which extracts the terms whose $t$-degree and $y$-degree are equal. A 1960s result expresses a power-series root $\varphi$ of $P(t,y)$, of multiplicity $e$, as the diagonal $\varphi=D\bigl(y^2\,\partial_y P(ty,y)/(e\,P(ty,y))\bigr)$. Over characteristic zero this becomes a closed coefficient-extraction sum, $\varphi(t)=\sum_{m\ge 1}\frac{1}{m}\,[y^{m-1}](y-P(t,y))^m$, which replaces iterative power-series lifting by a single finite expression: because every monomial of $y-P(t,y)$ is divisible by $t$ or by $y^2$, only $m\le 2d$ terms can affect the degree-$d$ truncation. That is what transfers size and depth bounds from $P$ to its roots. A second ingredient, a recent theorem on constant-depth circuits for elementary symmetric polynomials of values $g(\alpha_i)/h(\alpha_i)$ at the roots $\alpha_i$ of a degree-$d$ polynomial, is what converts a product of power-series roots over the algebraic closure into a factor with coefficients in the base field.

What would settle it

Check the theorem on which the lifting step rests at the precise instantiation used here: take $f(z)=z^d-1$ and let $g,h$ be polynomials produced by poly-size constant-depth circuits, then verify that the asserted constant-depth circuit for the elementary symmetric polynomials of $g(\alpha_i)/h(\alpha_i)$ exists over the base field without division gates or a PIT oracle. A concrete counterexample at this step, or any explicit family of constant-depth circuits whose irreducible factor can be shown to require super-polynomial size, would refute the main theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: over a field of characteristic zero, constant-depth algebraic circuits and algebraic formulas are closed under taking factors. If $f$ has degree $d$ and is computed by a circuit of size $s$ and depth $\Delta$, then every factor $g$ of $f$ is computed by a circuit of size $\mathrm{poly}(s,d,n)$ and depth $\Delta+O(1)$; if $f$ is computed by a formula of size $s$, then $g$ is computed by a formula of size $\mathrm{poly}(s,d,n)$. The proof first shows that truncations of a power-series root $\varphi(t)$ of $P(t,y)$, with $\varphi(0)=0$ and $\partial_y P(0,0)\ne 0$, are computable by the same kind of small circuit as $P$, using $\varphi(t)=\sum_{m\ge 1}\frac{1}{m}\,[y^{m-1}](y-P(t,y))^m$. It then combines these algebraic-closure roots into a factor over the base field with small constant-depth circuits for elementary symmetric polynomials of root evaluations. For finite fields the paper proves a weaker statement: if $g$ divides $f$ with multiplicity $p^\ell e$ and $\gcd(p,e)=1$, then $g^{p^\ell}$ has a poly-size constant-depth circuit over the algebraic closure.

Load-bearing premise

The proof leans on a recent external theorem asserting that, from the coefficients of $f,g,h$, one can build a $\mathrm{poly}(d)$-size, $O(1)$-depth circuit over the base field for every elementary symmetric polynomial of the values $g(\alpha_i)/h(\alpha_i)$ at the roots $\alpha_i$ of $f$; the closure argument needs this to remain true when $g$ and $h$ are themselves given by constant-depth circuits, and if that uniformity fails the lifting step has a gap.

Editorial extensions

If this is right

  • Every factor of an $n$-variate degree-$d$ polynomial computed by a size-$s$, depth-$\Delta$ constant-depth circuit is computed by a $\mathrm{poly}(s,d,n)$-size, depth-$\Delta+O(1)$ circuit.
  • Every factor of a size-$s$ algebraic formula is computed by a $\mathrm{poly}(s,d,n)$-size formula.
  • The standard hardness-randomness trade-off now applies to formulas and constant-depth circuits: sufficiently strong explicit lower bounds imply quasipolynomial-time deterministic identity testing for these classes.
  • Deterministic factorization of constant-depth circuits reduces to blackbox PIT for the same class, giving a deterministic subexponential-time factoring algorithm whose output circuits are also constant-depth, and a randomized polynomial-time factoring algorithm by random sampling.
  • The same proof yields a single argument covering closure for general circuits, formulas, branching programs, and VNP, and a border-complexity bound on low-degree factors of arbitrary circuits.

Reading between the lines

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

  • Because the root formula only needs coefficient extraction, interpolation, and homogenization, the same closure argument should transfer to any further algebraic model closed under these operations, such as read-once oblivious branching programs; this is an extension the paper does not work out.
  • The finite-field statement's restriction to $p^{\ell}$-th powers suggests that genuine closure failures, if any, live in the operation of taking $p$-th roots; the paper explicitly leaves open whether $f^p$ having a small constant-depth circuit forces $f$ to have one.
  • The proof's dependence on the factor degree $d$, rather than on the degree of $f$, is what yields the border bound for low-degree factors of high-degree circuits; pushing this direction may give a new route to the factor conjecture for general circuits.
  • The previous subexponential factoring algorithm for constant-depth circuits is now explained by the closure property itself: factors are constant-depth, so any explicit hitting set for constant-depth circuits preserves factorization; plugging in a better hitting set would immediately speed up deterministic factoring.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proves that constant-depth algebraic circuits and algebraic formulas over characteristic zero (and, with the same proof, sufficiently large characteristic) are closed under taking factors: if an n-variate degree-d polynomial f has a circuit of size s and depth Δ (resp. a formula of size s), then every factor g of f has a circuit of size poly(s,d,n) and depth Δ+O(1) (resp. a formula of size poly(s,d,n)). The main technical engine is a result of Furstenberg expressing power-series roots of a bivariate polynomial as the diagonal of a rational function; the paper gives a self-contained proof of this identity and uses it to show that truncations of power-series roots are computable by small constant-depth circuits and formulas. General factors are then recovered by combining power-series roots, using elementary symmetric functions and a theorem of Andrews and Wigderson. The paper also derives applications to deterministic factorization of constant-depth circuits, hardness-randomness trade-offs, and a border version of the factor conjecture.

Significance. If the proof is completed at the one black-box point identified below, this is a significant result: it resolves long-standing open questions about closure under factorization for formulas and constant-depth circuits, provides a unified proof of several known closure results, and yields clean quantitative improvements for deterministic factorization and hardness-randomness trade-offs. The paper is particularly valuable for giving an elementary, self-contained proof of Furstenberg's identity and for showing how a classical result can replace the iterative Newton/Hensel lifting that previously seemed essential. The applications in Sections 5--6 are natural and strengthen prior work. The main caveat is that the transition from power-series roots over the algebraic closure to factors over the base field relies on an external theorem whose uniformity and denominator behavior are not stated; this point is load-bearing but appears fixable.

major comments (3)
  1. [§4.2, Theorem 4.3] The recovery of the factor g(t,y) from the algebraic-closure roots applies Theorem 4.2 with f = g(0,y), g = Rnum, h = Rdenom, but this application is not covered by the quoted statement of that theorem. The quoted theorem assumes f,g,h ∈ F[z] with degree at most d and inputs 'coefficients from the base field'; here Rnum and Rdenom have coefficients in F[x,t] and deg_z(Rdenom) = (2d+3)·deg_z(∂_y P̃(0,z)) is O(d^2), exceeding the stated degree bound. The proof must state explicitly that Theorem 4.2 is uniform in the coefficients, so that the coefficient inputs may themselves be outputs of depth-Δ circuits; that the degree parameter is enlarged to O(d^2); and that the resulting circuit is either division-free or that all denominators are nonzero at the relevant coefficient tuples, or are explicitly cleared. As written, this is the only non-elementary step in the proof of the main closure theorem and it is load-bearing.
  2. [§4.2, display for g'(t,y)] The equalities g(t,y) = Hom_{≤d}(g'(t,y)) and g'(t,y) = ∏_{α∈S}(y−R(α)) initially define an object over the algebraic closure or over F(x,t). The argument that the coefficients of g' lie in F[x,t] and coincide with those of the original factor g is only implicit in the sentence that the elementary symmetric polynomials of {α : α∈S} are elements of the field. Base-field membership is exactly what makes Theorem 1.1 a statement over F rather than over an extension, so the proof should spell out why the symmetric-function circuit obtained from Theorem 4.2, after composing with the circuits for Rnum and Rdenom, computes a polynomial with coefficients in F[x,t] and why this polynomial agrees with g in all degrees up to the stated truncation.
  3. [§5.1, Lemma 5.1] The circuit C(x,t,y) used for the divisibility test is asserted to be a size-poly(s), depth-Δ+O(1) circuit because Q_U'(x,t,y) has that complexity. The construction of Q_U' uses the same symmetric-function step as Theorem 4.3, so the correctness of the deterministic algorithm in Theorem 5.2 inherits the same uniformity and denominator caveat. Since the algorithm's running time also depends on the time needed to construct the circuit from the coefficients, the paper should state whether the [AW24] theorem is constructive in the relevant sense; otherwise the algorithmic claim has the same gap.
minor comments (5)
  1. [References] The 'git info: 0c48f73...' line in the reference list appears to be a stray submission artifact and should be removed.
  2. [§1.1.1] There is a typo: 'demystefy' should be 'demystify'.
  3. [Definition 2.10] The definition of a valid pre-processing map says K = F(x) and Ψ_{a,b} : F[x,y] → K[t,y], but the displayed substitution xi ↦ t·xi + a_i y + b_i produces an element of F[x,t,y]. The role of K and the precise coefficient field should be clarified, since the later proof uses P̃(t,y) ∈ F[x][t,y] and P̃(0,y) ∈ F[y].
  4. [Theorem 1.1 / Theorem 4.2] The phrase 'zero or sufficiently large characteristic' is not quantified; the paper should state a concrete threshold, such as characteristic larger than d, so that the use of coefficients like 1/m in Corollary 3.3 is justified.
  5. [§5.1, proof of Lemma 5.1] The sentence 'distinct elements of F have distinct set of roots' appears to be a typo; it should refer to distinct roots of the squarefree polynomial F(0,0,y).

Circularity Check

0 steps flagged · score 2.0 of 10

The central closure proof is not circular: it derives factors from Furstenberg's diagonal identity and the external AW24 symmetric-function theorem; the only author-overlapping citations used in the proof are auxiliary non-load-bearing lemmas in the algorithmic section.

full rationale

Theorem 1.1 is derived in Section 4 without using the target closure statement as an hypothesis. Theorem 3.1, the Furstenberg identity, is proved in the paper directly from the factorization P=(y-phi)^e Q, and Corollary 3.3 and Theorem 4.1 obtain power-series roots by coefficient extraction, homogenization and interpolation. The transition from algebraic-closure roots to a base-field factor in Theorem 4.3 is made through the elementary symmetric polynomial circuit of Andrews and Wigderson, Theorem 4.2, which is an external theorem whose inputs are the coefficients of f, g and h and which does not assume the closure claim. No step fits a parameter from the target factor, and no equation defines the factor g in terms of its own circuit. The author-overlapping citations explicitly used as proof ingredients beyond background are Lemmas 5.4 and 5.5 from [BKR+25], employed in the deterministic factorization algorithm; these are technical structural and divisibility tools, not equivalent to closure under factorization, and their use does not make the central derivation depend on itself. The skeptic's concerns about Theorem 4.2's degree bound, denominator nonvanishing, and uniformity over coefficient circuits are correctness or gap checks rather than circularity, so they do not raise the score beyond the minor-self-citation level.

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

No free parameters are fitted to data. The proof relies on several external theorems from the algebraic complexity literature, most importantly the Andrews-Wigderson theorem on symmetric functions of roots, which is the main structural bridge from power series roots to factors over the base field. The paper proves Furstenberg's theorem in Section 3, so it is not a black-box assumption. No new mathematical entities are postulated.

assumptions (9)
  • standard math Furstenberg's diagonal identity (Theorem 3.1): phi = D( y^2 * partial_y P(ty,y) / (e P(ty,y)) ) when P=(y-phi)^e Q and Q(0,0) != 0.
    Proved in Section 3 from Furstenberg 1967; it is the starting point for Corollary 3.3, Theorem 4.1, and Theorem 4.3.
  • standard math Lagrange inversion corollary (Corollary 3.3): phi = sum_{m>=1} [y^{m-1}] { partial_y P(t,y) (y-P(t,y))^m } over fields where scalar m is invertible.
    Derived from Furstenberg's identity; the characteristic-zero version is also Stanley's exercise 5.59.
  • standard math Folklore factorization of monic polynomials into power series (Lemma 2.14).
    Used to associate each root alpha of P(0,y) to a unique power series root phi_alpha(t).
  • standard math Gauss Lemma, resultant and discriminant facts (Section 2.3).
    Used for pre-processing maps and squarefreeness arguments.
  • standard math Existence of valid pre-processing maps (Lemma 2.12 and Remark 2.13).
    A random linear substitution makes the polynomial monic in y and keeps P(0,y) squarefree; the factor correspondence is standard.
  • domain assumption Squarefree decomposition by constant-depth circuits (Theorem 2.15 of Andrews-Wigderson 2024).
    External theorem invoked to reduce to squarefree polynomials in Theorem 4.3 and in the deterministic algorithm.
  • domain assumption Symmetric functions of root evaluations are constant-depth computable (Theorem 4.2 of Andrews-Wigderson 2024).
    Load-bearing external theorem that turns algebraic-closure data into base-field elementary symmetric polynomials; used in Theorem 4.3 and Theorem 5.2.
  • domain assumption Explicit hitting-set generator for constant-depth circuits (Theorem 2.17 of Andrews-Forbes 2022).
    Used only in the deterministic factorization application (Theorem 5.2) to reduce the number of variables.
  • domain assumption Lemmas 5.4 and 5.5 from Bhattacharjee, Kumar, Ramanathan, Saptharishi and Saraf on factor structure and divisibility tests.
    Used in Section 5 to prove irreducibility preservation by the generator; these are technical lemmas from the authors' prior work, not equivalent to the closure claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Closure under factorization from a result of Furstenberg." pith.science (2026). https://pith.science/paper/AGSSWUCY

@misc{pith2026250623214,
  author       = {Pith},
  title        = {Pith review of: Closure under factorization from a result of Furstenberg},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AGSSWUCY}},
  note         = {Machine review of arXiv:2506.23214}
}
read the original abstract

We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. Our result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results. As applications, we get alternative (and perhaps simpler) proofs of various known results and strengthen the quantitative bounds in some of them. This includes a unified proof of known closure results for algebraic models (circuits, branching programs and VNP), an extension of the analysis of the Kabanets-Impagliazzo hitting set generator to formulas and constant-depth circuits, and a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits from a recent work of Bhattacharjee, Kumar, Ramanathan, Saptharishi & Saraf.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 18 canonical work pages

  1. [1]

    write newline toupdate empty

    " write newline toupdate empty "" write " toupdate(" cite * "): " * toupdate * " " * write if "" before.all 'output.state := FUNCTION fin.entry.original add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sen...

    work page

  2. [2]

    Robert Andrews and Michael A. Forbes. http://dx.doi.org/10.1145/3519935.3520025 Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals . In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 389--402. ACM , 2022

    arXiv

  3. [3]

    http://dx.doi.org/10.1109/FOCS61266.2024.00138 Constant-Depth Arithmetic Circuits for Linear Algebra Problems

    Robert Andrews and Avi Wigderson. http://dx.doi.org/10.1109/FOCS61266.2024.00138 Constant-Depth Arithmetic Circuits for Linear Algebra Problems . In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2367--2386, 2024

    arXiv 2024

  4. [4]

    Deterministic factorization of constant-depth algebraic circuits in subexponential time

    Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf. http://dx.doi.org/10.48550/ARXIV.2504.08063 Deterministic factorization of constant-depth algebraic circuits in subexponential time . CoRR , abs/2504.08063, 2025. Pre-print available at http://arxiv.org/abs/2504.08063 arXiv:2504.08063

    work page Pith review arXiv doi:10.48550/arxiv.2504.08063

  5. [5]

    http://dx.doi.org/10.1145/3365667 Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

    Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. http://dx.doi.org/10.1145/3365667 Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree . J. ACM , 67(2):8:1--8:28, 2020

    doi:10.1145/3365667 2020

  6. [6]

    http://dx.doi.org/10.1007/S10208-002-0059-5 The Complexity of Factors of Multivariate Polynomials

    Peter B \" u rgisser. http://dx.doi.org/10.1007/S10208-002-0059-5 The Complexity of Factors of Multivariate Polynomials . Found. Comput. Math. , 4(4):369--396, 2004

    doi:10.1007/s10208-002-0059-5 2004

  7. [7]

    http://dx.doi.org/10.4086/toc.2019.v015a013 Closure Results for Polynomial Factorization

    Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. http://dx.doi.org/10.4086/toc.2019.v015a013 Closure Results for Polynomial Factorization . Theory of Computing , 15(13):1--34, 2019

    doi:10.4086/toc.2019.v015a013 2019

  8. [8]

    http://dx.doi.org/10.1145/3510359 Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring

    Pranjal Dutta, Nitin Saxena, and Amit Sinhababu. http://dx.doi.org/10.1145/3510359 Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring . J. ACM , 69(3), June 2022

    doi:10.1145/3510359 2022

Show all 34 references
  1. [9]

    https://arxiv.org/abs/2411.17330 Derandomizing Multivariate Polynomial Factoring for Low Degree Factors , 2024

    Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf. https://arxiv.org/abs/2411.17330 Derandomizing Multivariate Polynomial Factoring for Low Degree Factors , 2024. Pre-print available at http://arxiv.org/abs/2411.17330 arXiv:2411.17330

    2024

  2. [10]

    http://dx.doi.org/10.1137/080735850 Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

    Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. http://dx.doi.org/10.1137/080735850 Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits . SIAM J. Comput. , 39(4):1279--1293, 2009

    2009 doi

  3. [11]

    Polynomial identity testing of read-once oblivious algebraic branching programs

    Michael Andrew Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs . PhD thesis, Massachusetts Institute of Technology, 2014

    2014

  4. [12]

    Michael A. Forbes. http://dx.doi.org/10.1109/FOCS.2015.35 Deterministic Divisibility Testing via Shifted Partial Derivatives . In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , FOCS '15, page 451–465, USA, 2015. IEEE Computer Society

    2015 doi

  5. [13]

    Forbes and Amir Shpilka

    Michael A. Forbes and Amir Shpilka. http://dx.doi.org/10.1145/2852040.2852051 Complexity Theory Column 88: Challenges in Polynomial Factorization1 . SIGACT News , 46(4):32–49, dec 2015

    2015

  6. [14]

    http://dx.doi.org/https://doi.org/10.1016/0021-8693(67)90061-0 Algebraic functions over finite fields

    Harry Furstenberg. http://dx.doi.org/https://doi.org/10.1016/0021-8693(67)90061-0 Algebraic functions over finite fields . Journal of Algebra , 7(2):271--277, 1967

    1967 doi

  7. [15]

    Ira M. Gessel. http://dx.doi.org/https://doi.org/10.1016/j.jcta.2016.06.018 Lagrange inversion . Journal of Combinatorial Theory, Series A , 144:212--249, 2016. Fifty Years of the Journal of Combinatorial Theory

    2016 doi

  8. [16]

    von zur Gathen and E

    J. von zur Gathen and E. Kaltofen. http://dx.doi.org/10.1016/0022-0000(85)90044-3 Factoring Sparse Multivariate Polynomials . Journal of Computer and System Sciences , 31(2):265--287, 1985

    1985 doi

  9. [17]

    Essential coding theory

    Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory . 2023

    2023

  10. [18]

    https://arxiv.org/abs/1611.01415 Explicit Implicit Function Theorem for All Fields , 2016

    Yining Hu. https://arxiv.org/abs/1611.01415 Explicit Implicit Function Theorem for All Fields , 2016. Pre-print available at http://arxiv.org/abs/1611.01415 arXiv:1611.01415

    2016 arXiv

  11. [19]

    Kaltofen

    Erich L. Kaltofen. http://dx.doi.org/10.1109/SFCS.1982.56 A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization . In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982 , pages 57--64. IEEE Co...

    1982 doi

  12. [20]

    http://dx.doi.org/10.1137/0214035 Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization

    Erich Kaltofen. http://dx.doi.org/10.1137/0214035 Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization . SIAM Journal of Computing , 14(2):469--489, 1985

    1985 doi

  13. [21]

    https://users.cs.duke.edu/ elk27/bibliography/89/Ka89_slpfac.pdf Factorization of Polynomials Given by Straight-Line Programs

    Erich Kaltofen. https://users.cs.duke.edu/ elk27/bibliography/89/Ka89_slpfac.pdf Factorization of Polynomials Given by Straight-Line Programs . In Randomness and Computation , pages 375--412. JAI Press, 1989

    1989

  14. [22]

    http://dx.doi.org/10.1007/s00037-004-0182-6 D erandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

    Valentine Kabanets and Russell Impagliazzo. http://dx.doi.org/10.1007/s00037-004-0182-6 D erandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds . Computational Complexity , 13(1-2):1--46, 2004. 2003

    2004 doi

  15. [23]

    http://dx.doi.org/10.48550/ARXIV.2309.09701 Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

    Mrinal Kumar, Varun Ramanathan, and Ramprasad Saptharishi. http://dx.doi.org/10.48550/ARXIV.2309.09701 Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits . CoRR , abs/2309.09701, 2023. Pre-print available at http://arxiv.org/abs/2309.09701 arXiv:2309.09701

    2023 doi arXiv

  16. [24]

    https://arxiv.org/abs/2403.01965 Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits , 2024

    Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, and Ben Lee Volk. https://arxiv.org/abs/2403.01965 Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits , 2024. Pre-print available at http://arxiv.org/abs/2403.01965 arXiv:2403.01965

    2024 arXiv

  17. [25]

    http://dx.doi.org/10.1007/s00037-015-0102-y Equivalence of Polynomial Identity Testing and Polynomial Factorization

    Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. http://dx.doi.org/10.1007/s00037-015-0102-y Equivalence of Polynomial Identity Testing and Polynomial Factorization . Computational Complexity , 24(2):295--331, 2015. 2014

    2015 doi

  18. [26]

    Kaltofen and Barry M

    Erich L. Kaltofen and Barry M. Trager. http://dx.doi.org/10.1109/SFCS.1988.21946 Computing with Polynomials Given By Black Boxes for Their Evaluation: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators . In 29th Annual Symposium on Foundations o...

    1988

  19. [27]

    http://dx.doi.org/https://doi.org/10.1016/j.jsc.2007.01.003 Improved dense multivariate polynomial factorization algorithms

    Grégoire Lecerf. http://dx.doi.org/https://doi.org/10.1016/j.jsc.2007.01.003 Improved dense multivariate polynomial factorization algorithms . Journal of Symbolic Computation , 42(4):477--494, 2007

    2007 doi

  20. [28]

    http://dx.doi.org/10.1109/FOCS52979.2021.00083 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

    Nutan Limaye, Srikanth Srinivasan, and S \' e bastien Tavenas. http://dx.doi.org/10.1109/FOCS52979.2021.00083 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits . In 2021 , pages 804--814. IEEE , 2021. 21 081

    2021

  21. [29]

    http://dx.doi.org/10.1007/S00037-016-0130-2 Factors of low individual degree polynomials

    Rafael Oliveira. http://dx.doi.org/10.1007/S00037-016-0130-2 Factors of low individual degree polynomials . Comput. Complex. , 25(2):507--561, 2016

    2016 doi

  22. [30]

    Alan D. Sokal. https://arxiv.org/abs/0902.0069 A ridiculously simple and explicit implicit function theorem , 2009. Pre-print available at http://arxiv.org/abs/0902.0069 arXiv:0902.0069

    2009 arXiv

  23. [31]

    http://dx.doi.org/10.4230/LIPIcs.CCC.2020.33 Factorization of Polynomials Given By Arithmetic Branching Programs

    Amit Sinhababu and Thomas Thierauf. http://dx.doi.org/10.4230/LIPIcs.CCC.2020.33 Factorization of Polynomials Given By Arithmetic Branching Programs . In 35th Computational Complexity Conference (CCC 2020) , volume 169 of Leibniz International Proceedings in Informatics (LIPIc...

    2020 doi

  24. [32]

    http://dx.doi.org/10.1017/CBO9780511609589 Enumerative Combinatorics - Volume 2

    Richard Stanley. http://dx.doi.org/10.1017/CBO9780511609589 Enumerative Combinatorics - Volume 2 . Cambridge University Press, 1999

    1999 doi

  25. [33]

    http://dx.doi.org/10.1080/00029890.2023.2251344 Lagrange Inversion Formula by Induction

    Erlang Surya and Lutz Warnke. http://dx.doi.org/10.1080/00029890.2023.2251344 Lagrange Inversion Formula by Induction . The American Mathematical Monthly , 130(10):944--948, 2023. Pre-print available at http://arxiv.org/abs/2305.17576 arXiv:2305.17576

    2023

  26. [34]

    http://dx.doi.org/10.1017/CBO9781139856065 Modern Computer Algebra

    Joachim von zur Gathen and Jürgen Gerhard. http://dx.doi.org/10.1017/CBO9781139856065 Modern Computer Algebra . Cambridge University Press, 3 edition, 2013

    2013 doi

Pith tools

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