Pith. sign in

REVIEW 1 cited by

A primer on the closure of algebraic complexity classes under factoring

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2506.19604 v2 pith:PJOUM3DT submitted 2025-06-24 cs.CC

C. S. Bhargav , Prateek Dwivedi , Nitin Saxena This is my paper
classification cs.CC
keywords textcomplexitypolynomialalgebraiccircuitsclassestechniquesdegree
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Polynomial factorisation is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their computational hardness. This raises a natural question: Are these complexity classes closed under factorisation? In this survey, we revisit pivotal techniques in polynomial factorisation: Hensel lifting, Newton iteration, and Lagrange inversion. These techniques have played an essential role in resolving key factoring questions in algebraic complexity for more than half a century. We examine and organise the known results through the lens of these techniques, discussing their underlying mathematical equivalence while reflecting on how their applications vary depending on the problem context. We focus on prominent algebraic complexity classes, including $\text{VP}$ (circuits of polynomial size and degree), its closure $\overline{\text{VP}}$, the class $\text{VNP}$ (verifier circuits of polynomial size and degree), $\text{VBP}$ (polynomial-size branching programs), $\text{VF}$ (polynomial-size formulas), and $\text{VP}_{\text{nb}}$ (circuits of polynomial size and exponential degree). We also discuss bounded-depth circuits and sparse polynomials. Along the way, we highlight several unresolved open problems.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Deterministic Algorithms for Low Individual Degree Factors of Sparse Polynomials

    cs.CC 2026-06 unverdicted novelty 7.0 of 10

    Deterministic poly-time and quasipoly-time algorithms list all bounded individual-degree factors of sparse polynomials (with possible spurious outputs) and yield a new upper bound on their number.

Reference graph

Works this paper leans on

38 extracted references · 14 canonical work pages · cited by 1 Pith paper

  1. [1]

    Proving Lower Bounds via Pseudo-Random Gen- erators

    [AB09] Sanjeev Arora and Boaz Barak.Computational Complexity. Cambridge University Press, Cambridge, 2009 (cit. on pp. 4, 9). [Agr05] Manindra Agrawal. “Proving Lower Bounds via Pseudo-Random Gen- erators”. In: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science. Vol

    2009

  2. [7]

    Cook’s versus Valiant’s Hypothesis

    Algorithms and Computation in Mathematics. Springer- Verlag, Berlin, 2000 (cit. on pp. 9, 31, 39). Bhargav, Dwivedi & Saxena 53 [B¨ ur00b] Peter B¨ urgisser. “Cook’s versus Valiant’s Hypothesis”. In: Theoret. Comput. Sci. 235 (2000), pp. 71–88 (cit. on p. 9). [B¨ ur04] Peter B¨ urgisser. “The Complexity of Factors of Multivariate Polyno- mials”. In: Found...

    2000

  3. [10]

    On the Structure of Valiant’s Complexity Classes

    arXiv: 2406.06217 [cs] (cit. on p. 8). [B¨ ur99] Peter B¨ urgisser. “On the Structure of Valiant’s Complexity Classes”. In: Discrete Math. Theor. Comput. Sci.3.3 (1999), pp. 73–94 (cit. on p. 9). [CDS24] Sayak Chakrabarti, Ashish Dwivedi, and Nitin Saxena. “Solving Polyno- mial Systems over Non-Fields and Applications to Modular Polynomial Factoring”. In:...

    arXiv 1999

  4. [15]

    Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

    LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024, Art. No. 75, 20 (cit. on p. 38). [DSY09] Zeev Dvir,Amir Shpilka,and Amir Yehudayoff. “Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits”. In:SIAM J. Comput. 39.4 (2009), pp. 1279–1293 (cit. on pp. 35, 36). [For+21] Michael A. Forbes, Amir Shpilka, I...

    2009

  5. [17]

    Eine Neue Theorie Der Algebraischen Zahlen

    BG Teubner, 1908 (cit. on p. 15). [Hen18] Kurt Hensel. “Eine Neue Theorie Der Algebraischen Zahlen”. In:Math. Z. 2.3-4 (1918), pp. 433–452 (cit. on p. 15). Bhargav, Dwivedi & Saxena 57 [Hen97] Kurt Hensel. “¨Uber eine neue Begr¨ undung der Theorie der algebraischen Zahlen.” In: Jahresbericht der Deutschen Mathematiker-Vereinigung6 (1897), pp. 83–88 (cit. ...

    1918

  6. [25]

    arXiv: 2403.01965 [cs] (cit. on p. 38). [Lan17] J. M. Landsberg. Geometry and Complexity Theory . Vol

    arXiv

  7. [26]

    Factoring Polynomials with Rational Coefficients

    Cam- bridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2017 (cit. on p. 41). [LLL82] A. K. Lenstra, H. W. Lenstra Jr., and L. Lov´asz. “Factoring Polynomials with Rational Coefficients”. In: Math. Ann. 261.4 (1982), pp. 515–534 (cit. on p. 21). [LS78] Richard J. Lipton and Larry J. Stockmeyer. “Evaluation of Polynomials with S...

    work page 1982

  8. [27]

    Factorization of Polynomials

    Algorithms and Combinatorics. Springer, Heidelberg, 2012 (cit. on p. 15). [Kal82] Erich Kaltofen. “Factorization of Polynomials”. In: Computer Algebra: Symbolic and Algebraic Computation. Vienna: Springer, 1982, pp. 95– 113 (cit. on p. 3). [Kal85] Erich Kaltofen. “Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Facto...

    1985

Show all 38 references
  1. [28]

    Polynˆomes et coefficients

    Progr. Comput. Sci. Appl. Logic. Birkh¨auser/Springer, Cham, 2014, pp. 51–75 (cit. on pp. 9, 28). [Mal03] Guillaume Malod. “Polynˆomes et coefficients”. PhD thesis. Universit´e Claude Bernard - Lyon, 2003 (cit. on p. 39). [Mal07] Guillaume Malod. “The Complexity of Polynomials...

    2008

  2. [29]

    Progr. Comput. Sci. Appl. Logic. Birkh¨auser/Springer, Cham, 2014, pp. 131–146 (cit. on p. 11). [Sax23] Nitin Saxena.Closure of Algebraic Classes Under Factoring

    2014

  3. [30]

    Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials

    Monogr. Enseign. Math. Univ. Gen`eve, Geneva, 1982, pp. 365–380 (cit. on pp. 8, 32). [Vol15] Ilya Volkovich. “Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials”. In:Approxi- mation, Randomization, and Combinatorial Optim...

    1982

  4. [40]

    On Some Computations on Sparse Polynomials

    LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, pp. 943–958 (cit. on p. 48). [Vol17] Ilya Volkovich. “On Some Computations on Sparse Polynomials”. In: Approximation, Randomization, and Combinatorial Optimization. Al- gorithms and Techn...

    2015

  5. [50]

    Power series in complexity: Algebraic Dependence, Factor Conjecture and Hitting Set for Closure of VP

    LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 31, 53 (cit. on p. 15). 62 Closure of algebraic complexity classes [Sin19] Amit Sinhababu. “Power series in complexity: Algebraic Dependence, Factor Conjecture and Hitting Set fo...

    2016

  6. [60]

    Deter- ministic Algorithms for Low Degree Factors of Constant Depth Circuits

    Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 1995 (cit. on p. 15). [KRS24] Mrinal Kumar, Varun Ramanathan, and Ramprasad Saptharishi. “Deter- ministic Algorithms for Low Degree Factors of Constant Depth Circuits”. In: Proceedings of ...

    2006

  7. [72]

    Newton’s Iteration and the Sparse Hensel Algorithm (Extended Abstract)

    Lecture Notes in Comput. Sci. Springer, Berlin-New York, 1979, pp. 216–226 (cit. on p. 11). [Zip81] Richard Zippel. “Newton’s Iteration and the Sparse Hensel Algorithm (Extended Abstract)”. In: Proceedings of the Fourth ACM Symposium on Symbolic and Algebraic Computation. SYMS...

    1979

  8. [77]

    Fast Probabilistic Algorithms for Verification of Poly- nomial Identities

    Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 2000 (cit. on p. 48). [Sch80] J. T. Schwartz. “Fast Probabilistic Algorithms for Verification of Poly- nomial Identities”. In: J. ACM 27.4 (1980), pp. 701–717 (cit. on p. 11). [Sho09] Vict...

    1980

  9. [80]

    Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring

    Advances in Information Security. Springer, New York, 2020 (cit. on p. 15). [DSS22] Pranjal Dutta, Nitin Saxena, and Amit Sinhababu. “Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring”. In: J. ACM 69.3 (2022), Art. 18, 39 (cit. on pp. 34, 40,...

    2022

  10. [81]

    Hensel Meets Newton–Algebraic Constructions in an Analytic Setting

    LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, Art. No. 48, 21 (cit. on p. 48). [Yun76] David Y. Y. Yun. “Hensel Meets Newton–Algebraic Constructions in an Analytic Setting”. In: Analytic Computational Complexity (Proc. Sym- pos., Car...

    2017

  11. [169]

    Leibniz Int

    LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, Art. No. 37, 32 (cit. on pp. 13, 27, 33). [Art22] Michael Artin. Algebraic Geometry—Notes on a Course . Vol

    2020

  12. [170]

    Cambridge University Press, Cambridge, 2019 (cit

    Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 2019 (cit. on p. 15). [Kra95] Jan Kraj´ıˇcek. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Vol

    2019

  13. [215]

    Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 118:1–118:33 (cit

    Leibniz Interna- tional Proceedings in Informatics (Lipics). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 118:1–118:33 (cit. on p. 15). [SS25] Shubhangi Saraf and Devansh Shringi. Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$

    2022

  14. [222]

    Improved Low-Degree Testing and Its Applications

    Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2022 (cit. on pp. 35, 45). [AS03] Sanjeev Arora and Madhu Sudan. “Improved Low-Degree Testing and Its Applications”. In: Combinatorica 23.3 (2003), pp. 365–426 (cit. on p. 15). [A V08] Manindra Agr...

    2003

  15. [315]

    Learning the Coef- ficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring

    Grundlehren Der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1997 (cit. on p. 9). 52 Closure of algebraic complexity classes [BDS24] C. S. Bhargav, Prateek Dwivedi, and Nitin Saxena. “Learning the Coef- ficients: A P...

    1997

  16. [317]

    A Probabilistic Remark on Algebraic Program Testing

    LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024, Art. No. 44, 19 (cit. on p. 15). [DL78] Richard A. DeMillo and Richard J. Lipton. “A Probabilistic Remark on Algebraic Program Testing”. In: Inf. Process. Lett. 7.4 (1978), pp. 193– 195 (...

    1978

  17. [583]

    Effective Noether Irreducibility Forms and Applica- tions

    Lecture Notes in Comput. Sci. Springer, Berlin, 1992, pp. 294–313 (cit. on p. 3). [Kal95] Erich Kaltofen. “Effective Noether Irreducibility Forms and Applica- tions”. In: J. Comput. System Sci. 50.2 (1995), pp. 274–295 (cit. on p. 25). [KI04] Valentine Kabanets and Russell Imp...

    1995

  18. [1838]

    Efficient Factorization of Polynomials over Local Fields

    Lecture Notes in Comput. Sci. Springer, Berlin, 2000, pp. 185–208 (cit. on p. 22). [Chi87] A. L. Chistov. “Efficient Factorization of Polynomials over Local Fields”. In: Doklady Akademii Nauk SSSR 293.5 (1987), pp. 1073–1077 (cit. on p. 22). [CKS19a] Chi-Ning Chou, Mrinal Kuma...

    1987

  19. [1858]

    Derandomization via Symmetric Poly- topes: Poly-time Factorization of Certain Sparse Polynomials

    Lecture Notes in Comput. Sci. Springer, Berlin, 2000, pp. 3– 22 (cit. on p. 15). [BS25] Pranav Bisht and Nitin Saxena. “Derandomization via Symmetric Poly- topes: Poly-time Factorization of Certain Sparse Polynomials”. In:ACM Trans. Comput. Theory 17.2 (2025), 12:1–12:20 (cit....

    2025

  20. [1903]

    Closure Results for Polynomial Factorization

    02366 [cs] (cit. on p. 45). [CKS19b] Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. “Closure Results for Polynomial Factorization”. In:Theory Comput. 15 (2019), Paper No. 13, 34 (cit. on pp. 31, 32, 34, 38, 46). [CKW10] Xi Chen, Neeraj Kayal, and Avi Wigderson. “Partial Deriva...

    2019

  21. [2008]

    Factoring High-Degree Polyno- mials by the Black Box Berlekamp Algorithm

    ACM, New York, 2008, pp. 141–146 (cit. on p. 29). [KL94] Erich L. Kaltofen and Austin Lobo. “Factoring High-Degree Polyno- mials by the Black Box Berlekamp Algorithm”. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC ’94. ACM, 1994, p...

    2012

  22. [2011]

    87–100 (cit

    Tsinghua University Press, 2011, pp. 87–100 (cit. on p. 29). [Juk12] Stasys Jukna. Boolean Function Complexity. Vol

    2011

  23. [2013]

    Complexity Theory Column 88: Challenges in Polynomial Factorization

    IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 243–252 (cit. on p. 12). [FS15] Michael A. Forbes and Amir Shpilka. “Complexity Theory Column 88: Challenges in Polynomial Factorization”. In: ACM SIGACT News46.4 (2015), pp. 32–49 (cit. on pp. 3, 12, 15). [Gat06] Joachim von zur...

    2015

  24. [2014]

    Lecture notes, Rutgers University (cit. on p. 6). [KP13] Steven G. Krantz and Harold R. Parks. The Implicit Function Theorem. Modern Birkh¨auser Classics. Birkh¨auser/Springer, New York, 2013 (cit. on p. 35). [Kra19] Jan Kraj´ıˇcek. Proof Complexity. Vol

    2013

  25. [2023]

    Talk at Recent Trends in Computer Algebra (2023) in Institut Henri Poincar´e, Paris. (Cit. on p. 50). [Sch00] Andrzej Schinzel. Polynomials with Special Regard to Reducibility . Vol

    2023

  26. [2024]

    2367–2386 (cit

    IEEE Com- puter Society, 2024, pp. 2367–2386 (cit. on p. 39). [BCS97] Peter B¨ urgisser, Michael Clausen, and M. Amin Shokrollahi. Alge- braic Complexity Theory. Vol

    2024

  27. [2025]

    A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

    Electronic Colloquium on Computational Complexity: TR25-008 (cit. on p. 15). [SSS13] Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. “A Case of Depth-3 Identity Testing, Sparse Factorization and Duality”. In:Comput. Complexity 22.1 (2013), pp. 39–69 (cit. on p. 11). [ST...

    2013

  28. [2504]

    Introduction to Geometric Complexity Theory

    08063 [cs] (cit. on pp. 39, 50). [BI25] Markus Bl ¨aser and Christian Ikenmeyer. “Introduction to Geometric Complexity Theory”. In: Theory Comput. Graduate Surveys 10 (2025), p. 166 (cit. on p. 41). [BIZ18] Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. “On Alge- bra...

    2025

  29. [3821]

    Determinant versus Permanent

    Lecture Notes in Comput. Sci. Springer, Berlin, 2005, pp. 92–105 (cit. on p. 12). [Agr06] Manindra Agrawal. “Determinant versus Permanent”. In: International Congress of Mathematicians. Vol. III . Eur. Math. Soc., Z¨ urich, 2006, pp. 985–997 (cit. on p. 9). [AGS19] Manindra Ag...

    2019

  30. [6198]

    Arithmetic Circuits: A Survey of Recent Results and Open Questions

    Lecture Notes in Comput. Sci. Springer, Berlin, 2010, pp. 408–419 (cit. on pp. 11, 48). [SY10] Amir Shpilka and Amir Yehudayoff. “Arithmetic Circuits: A Survey of Recent Results and Open Questions”. In:Found. Trends Theor. Comput. Sci. 5.3-4 (2010), 207–388 (2010) (cit. on pp....

    2010

Pith tools