Factorization of Polynomials Given by Arithmetic Branching Programs

Stuart J. Berkowitz (1984). On computing the determinant in small parallel time using a small number of processors. Information processing letters 18(3), 147–150 Peter Bürgisser (2004). The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics 4(4), 369–396. Peter Bürgisser (2013). Completeness and reduction in algebraic complexity theory, volume 7 of Algorithms and Computation in Mathematic. Springer. Alexander L. Chistov (1985). Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. In International Conference on Fundamentals of Computation Theory, 63–69. Springer. Chi-Ning Chou, Mrinal Kumar & Noam Solomon (2019a). Closure of VP under taking factors: a short and simple proof. Technical Report arXiv:1903.02366, arXiv. Chi-Ning Chou, Mrinal Kumar & Noam Solomon (2019b). Closure Results for Polynomial Factorization. Theory of Computing 15(13),1–34. L. Csanky (1976). Fast Parallel Matrix Inversion Algorithms. SIAM Journal on Computing 5(4), 618–623. Pranjal Dutta (2018). Discovering the roots: Unifying and extending results on multivariate polynomial factoring in algebraic complexity. Master’s thesis, Chennai Mathematical Institute. Pranjal Dutta, Nitin Saxena & Amit Sinhababu (2018). Discovering the roots: Uniform closure results for algebraic classes under factoring. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 1152–1165. ACM. Michael A. Forbes & Amir Shpilka (2015). Complexity Theory Column 88: Challenges in Polynomial Factorization. ACM SIGACT News 46(4), 32–49 Michael A. Forbes, Amir Shpilka, Iddo Tzameret & Avi Wigderson (2016). Proof complexity lower bounds from algebraic circuit complexity. In Proceedings of the 31st Conference on Computational Complexity (CCC), 32. LIPIcs. Günther Frei (2005). The Unpublished Section Eight: On the Way to Function Fields over a Finite Field. In The Shaping of Arithmetic after C. F. Gauß’ Disquisitiones Arithmeticae, chapter II.4, 159–198. Springer. Joachim von zur Gathen (1984). Hensel and Newton methods in valuation rings. Mathematics of Computation 42(166), 637–661. Joachim von zur Gathen & Jürgen Gerhard (2013). Modern Computer Algebra. Cambridge University Press. Carl Friedrich Gauß (1870). Werke, Band II, zweiter Abdruck. Dietrich, Göttingen. Keith O. Geddes, Stephen R. Czapor & George Labahn (1992). Algorithms for Computer Algebra. Springer Science & Business Media. Kurt Hensel (1899). Über eine neue Begründung der Theorie der algebraischen Zahlen. In Jahresbericht der Deutschen Mathematiker- Vereinigung, volume 6, 83–88. Teubner. Kurt Hensel (1904). Neue Grundlagen der Arithmetik. Journal für die reine und angewandte Mathematik 127, 51–84. Kurt Hensel (1908). Theorie der algebraischen Zahlen. Teubner. Kurt Hensel (1918). Eine neue Theorie der algebraischen Zahlen. Mathematische Zeitschrift 2, 433–452. Valentine Kabanets & Russell Impagliazzo (2004). Derandomizing polynomial identity tests means proving circuit lower bounds. computational complexity 13(1–2), 1–46. Erich Kaltofen (1986). Uniform Closure Properties of P-Computable Functions. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), 330–337. Erich Kaltofen (1987). Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. In Proceedings of the 19th annual ACM Symposium on Theory of Computing (STOC), 443–452. ACM. Erich Kaltofen (1989). Factorization of polynomials given by straight-line programs. Randomness and Computation 5, 375–412. Erich Kaltofen (1995). Effective Noether irreducibility forms and applications. Journal of Computer and System Sciences 50(2), 274–295. Erich Kaltofen & Pascal Koiran (2008). Expressing a fraction of two determinants as a determinant. In Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation, 141–146. ACM. Erich Kaltofen & Barry M. Trager (1990). Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation 9(3), 301–320. Swastik Kopparty, Shubhangi Saraf & Amir Shpilka (2015). Equivalence of polynomial identity testing and polynomial factorization. computational complexity 24(2), 295–331. Mrinal Kumar & Ramprasad Saptharishi (2019). Hardness-Randomness Tradeoffs for Algebraic Computation. Bulletin of EATCS 3(129). Meena Mahajan (2014). Algebraic complexity classes. In Perspectives in Computational Complexity, 51–75. Springer. Meena Mahajan & V Vinay (1999). Determinant: Old algorithms, new insights. SIAM Journal on Discrete Mathematics 12(4), 474–490. Rafael Oliveira (2016). Factors of low individual degree polynomials. computational complexity 2(25), 507–561. Ramprasad Saptharishi (2021). A survey of lower bounds in arithmetic circuit complexity. https://github.com/dasarpmar/lowerbounds-survey/releases. Tateaki Sasaki & Masayuki Suzuki (1992). Three new algorithms for multivariate polynomial GCD. Journal of symbolic computation 13(4), 395–411. Amir Shpilka & Ilya Volkovich (2010). On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. In International Colloquium on Automata, Languages and Programming, 408–419. Springer. Madhu Sudan (1998). Algebra and Computation. http://people.csail.mit.edu/madhu/FT98/course.html. Lecture Notes. Hans Zassenhaus (1969). On Hensel factorization, I. Journal of Number Theory 1(3), 291–311.