Document Open Access Logo

Factorization of Polynomials Given By Arithmetic Branching Programs

Authors Amit Sinhababu, Thomas Thierauf

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.33.pdf
  • Filesize: 0.49 MB
  • 19 pages

Document Identifiers

Author Details

Amit Sinhababu
  • Aalen University, Germany
Thomas Thierauf
  • Aalen University, Germany

Funding

Research supported by DFG grant TH 472/5-1.

Acknowledgements

We thank Nitin Saxena, Pranjal Dutta, Arpita Korwar, Sumanta Ghosh, Zeyu Guo and Mrinal Kumar for helpful discussions. A.S would like to thank the Institute of Theoretical Computer Science at Ulm University for the hospitality.

Cite AsGet BibTex

Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.33

Abstract

Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s^(log s)).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Arithmetic Branching Program
  • Multivariate Polynomial Factorization
  • Hensel Lifting
  • Newton Iteration
  • Hardness vs Randomness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Peter Bürgisser. The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics, 4(4):369-396, 2004. Google Scholar
  2. Peter Bürgisser. Completeness and reduction in algebraic complexity theory, volume 7 of Algorithms and Computation in Mathematic. Springer, 2013. Google Scholar
  3. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Closure of VP under taking factors: a short and simple proof. Technical Report arXiv:1903.02366, arXiv, 2019. URL: http://arxiv.org/abs/1903.02366.
  4. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Closure results for polynomial factorization. Theory of Computing, 15(13):1-34, 2019. URL: https://doi.org/10.4086/toc.2019.v015a013.
  5. Pranjal Dutta. Discovering the roots: Unifying and extending results on multivariate polynomial factoring in algebraic complexity. Master’s thesis, Chennai Mathematical Institute, 2018. Google Scholar
  6. Pranjal Dutta, Nitin Saxena, and Amit Sinhababu. 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), pages 1152-1165. ACM, 2018. Google Scholar
  7. Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. Proof complexity lower bounds from algebraic circuit complexity. In Proceedings of the 31st Conference on Computational Complexity (CCC), page 32. LIPIcs, 2016. Google Scholar
  8. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pages 355-364. ACM, 2003. Google Scholar
  9. Erich Kaltofen. Uniform closure properties of p-computable functions. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pages 330-337, 1986. Google Scholar
  10. Erich Kaltofen. 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), pages 443-452. ACM, 1987. Google Scholar
  11. Erich Kaltofen. Factorization of polynomials given by straight-line programs. Randomness and Computation, 5:375-412, 1989. Google Scholar
  12. Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and polynomial factorization. computational complexity, 24(2):295-331, 2015. Google Scholar
  13. Mrinal Kumar and Ramprasad Saptharishi. Hardness-randomness tradeoffs for algebraic computation. Bulletin of EATCS, 3(129), 2019. Google Scholar
  14. Meena Mahajan. Algebraic complexity classes. In Perspectives in Computational Complexity, pages 51-75. Springer, 2014. Google Scholar
  15. Meena Mahajan and V Vinay. Determinant: Old algorithms, new insights. SIAM Journal on Discrete Mathematics, 12(4):474-490, 1999. Google Scholar
  16. Rafael Oliveira. Factors of low individual degree polynomials. computational complexity, 2(25):507-561, 2016. Google Scholar
  17. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. https://github.com/dasarpmar/lowerbounds-survey/releases, 2016.
  18. Madhu Sudan. Algebra and computation. http://people.csail.mit.edu/madhu/FT98/course.html, 1998. Lecture Notes.
  19. Joachim von zur Gathen. Hensel and Newton methods in valuation rings. Mathematics of Computation, 42(166):637-661, 1984. Google Scholar
  20. Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 2013. Google Scholar
  21. Hans Zassenhaus. On Hensel factorization, I. Journal of Number Theory, 1(3):291-311, 1969. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact