Document Open Access Logo

Arithmetic Circuit Complexity of Division and Truncation

Authors Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.25.pdf
  • Filesize: 0.99 MB
  • 36 pages

Document Identifiers

Author Details

Pranjal Dutta
  • Chennai Mathematical Institute, India
Gorav Jindal
  • Institut für Mathematik, Technische Universität Berlin, Germany
Anurag Pandey
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Amit Sinhababu
  • Aalen University, Germany

Funding

  • Dutta, Pranjal: Supported by Google Ph. D. Fellowship.
  • Jindal, Gorav: Supported by Graduiertenkolleg "Facets of Complexity/Facetten der Komplexität" (GRK 2434).
  • Sinhababu, Amit: Supported by DFG grant TH 472/5-1.

Acknowledgements

We thank Himanshu Shukla for several discussions on the complexity of truncated power series, and for bringing the reference [Coons and Borwein, 2008] to our attention. P. D. would like to thank CSE, IIT Kanpur for the hospitality. A. S. would like to thank the Institute of Theoretical Computer Science at Ulm University for the hospitality. We thank Thomas Thierauf and Nitin Saxena for discussions and feedback on the draft.

Cite AsGet BibTex

Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu. Arithmetic Circuit Complexity of Division and Truncation. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 25:1-25:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.25

Abstract

Given polynomials f,g,h ∈ 𝔽[x₁,…,x_n] such that f = g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s,deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 & WACT'16). The result is an exponential improvement over Strassen’s classic result (Strassen'73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). Further, we show that any univariate polynomial family (f_d)_d, defined by the initial segment of the power series expansion of rational function g_d(x)/h_d(x) up to degree d (i.e. f_d = g_d/h_d od x^{d+1}), where circuit size of g is s_d and degree of g_d is at most d, can be computed by a circuit of size poly(s_d,deg(h_d),log d). We also show a hardness result when the degrees of the rational functions are high (i.e. Ω (d)), assuming hardness of the integer factorization problem. Finally, we extend this conditional hardness to simple algebraic functions as well, and show that for every prime p, there is an integral algebraic power series with its minimal polynomial satisfying a degree p polynomial equation, such that its initial segment is hard to compute unless integer factoring is easy, or a multiple of n! is easy to compute. Both, integer factoring and computation of multiple of n!, are believed to be notoriously hard. In contrast, we show examples of transcendental power series whose initial segments are easy to compute.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Arithmetic Circuits
  • Division
  • Truncation
  • Division elimination
  • Rational function
  • Algebraic power series
  • Transcendental power series
  • Integer factorization

Metrics

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

References

  1. Alexander Alder. Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht. PhD thesis, Zentralstelle der Studentenschaft, 1984. Google Scholar
  2. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Miltersen. On the Complexity of Numerical Analysis. SIAM Journal on Computing, 38, January 2006. Preliminary version in the 21^st Annual IEEE Conference on Computational Complexity (CCC'06). URL: https://doi.org/10.1109/CCC.2006.30.
  3. Robert Andrews. Algebraic Hardness Versus Randomness in Low Characteristic. In 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 37:1-37:32. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.37.
  4. Jean Berstel and Christophe Reutenauer. Rational Series and Their Languages. Springer-Verlag, Berlin, Heidelberg, 1988. URL: https://dl.acm.org/doi/book/10.5555/52107.
  5. Markus Bläser and Gorav Jindal. On the Complexity of Symmetric Polynomials. In 10^th Innovations in Theoretical Computer Science Conference (ITCS'19), volume 124 of LIPIcs, pages 47:1-47:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.47.
  6. Alin Bostan, Gilles Christol, and Philippe Dumas. Fast computation of the Nth term of an algebraic series over a finite prime field. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC'16), pages 119-126, 2016. URL: https://doi.org/10.1145/2930889.2930904.
  7. Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On Algebraic Branching Programs of Small Width. J. ACM, 65(5):1-29, 2018. (Preliminary version in the 32^nd Computational Complexity Conference (CCC'17). URL: https://doi.org/10.1145/3209663.
  8. Peter Bürgisser. The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics, 4(4):369-396, 2004. URL: http://arxiv.org/abs/1812.06828.
  9. Peter Bürgisser. On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18(1):81-103, 2009. URL: https://doi.org/10.1007/s00037-009-0260-x.
  10. Peter Bürgisser, Michael Clausen, and Amin Shokrollahi. Algebraic complexity theory, volume 315. Springer Science & Business Media, 2013. Google Scholar
  11. David V Chudnovsky and Gregory V Chudnovsky. On expansion of algebraic functions in power and Puiseux series, I. Journal of Complexity, 2(4):271-294, 1986. URL: https://www.sciencedirect.com/science/article/pii/0885064X86900063.
  12. Michael Coons. The Transcendence of Series Related to Stern’s Diatomic Sequence. International Journal of Number Theory, 06, November 2011. URL: https://doi.org/10.1142/S1793042110002958.
  13. Michael Coons and Peter Borwein. Transcendence of power series for some number theoretic functions. Proceedings of the American Mathematical Society, 137, July 2008. URL: https://doi.org/10.1090/S0002-9939-08-09737-2.
  14. Wellington De Melo and Benar Fux Svaiter. The cost of computing integers. Proceedings-American Mathematical Society, 124:1377-1378, 1996. URL: https://www.ams.org/journals/proc/1996-124-05/S0002-9939-96-03173-5/S0002-9939-96-03173-5.pdf.
  15. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://www.sciencedirect.com/science/article/abs/pii/0020019078900674.
  16. Pranjal Dutta. Real tau-Conjecture for sum-of-squares: A unified approach to lower bound and derandomization. In 16th International Computer Science Symposium in Russia (CSR 2021), 2021. URL: https://drive.google.com/file/d/1X8eo9GM4SCNsC2vWjPbUwMX0vff5i2k3/view.
  17. 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, pages 1152-1165, 2018. URL: https://www.cse.iitk.ac.in/users/nitin/papers/factor-closure.pdf.
  18. Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1-23:21. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.23.
  19. Joshua A Grochow et al. Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs. Bulletin of EATCS, 2(130), 2020. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/607.
  20. Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, pages 34:1-34:14, 2016. URL: https://core.ac.uk/download/pdf/62922137.pdf.
  21. Gorav Jindal. On approximate polynomial identity testing and real root finding. PhD thesis, Saarland University, 2019. URL: https://doi.org/10.22028/D291-29880.
  22. Erich Kaltofen. Uniform closure properties of p-computable functions. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 330-337, 1986. URL: https://doi.org/10.1145/12130.12163.
  23. Erich Kaltofen. Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. In Proceedings of the 19^th annual ACM symposium on Theory of computing (STOC'87), pages 443-452, 1987. URL: https://doi.org/10.1145/28395.28443.
  24. Pascal Koiran. Valiant’s model and the cost of computing integers. computational complexity, 13(3):131-146, 2005. Google Scholar
  25. Pascal Koiran. Shallow circuits with high-powered inputs. Innovations in Computer Science (ICS), 2011. URL: https://hal-ens-lyon.archives-ouvertes.fr/ensl-00477023v4/document.
  26. Pascal Koiran and Sylvain Perifel. Interpolation in Valiant’s theory. Computational Complexity, 20(1):1-20, 2011. URL: https://doi.org/10.1007/s00037-011-0002-8.
  27. Pascal Koiran, Natacha Portier, Sébastien Tavenas, and Stéphan Thomassé. A τ-Conjecture for Newton Polygons. Foundations of computational mathematics, 15(1):185-197, 2015. URL: https://doi.org/10.1007/s10208-014-9216-x.
  28. FV Kuhlmann. On convergent power series, 1996. URL: https://www.mathi.uni-heidelberg.de/~roquette/KONVPOTREIHEN.pdf.
  29. Hsiang Kung and Joseph Traub. All Algebraic Functions Can Be Computed Fast. J. ACM, 25:245-260, April 1978. URL: https://doi.org/10.1145/322063.322068.
  30. Dick Lipton and Ken Regan. Factoring and factorials, February 2009. URL: https://rjlipton.wordpress.com/2009/02/23/factoring-and-factorials/.
  31. Richard J Lipton. Polynomials with 0-1 coefficients that are hard to evaluate. SIAM Journal on Computing, 7(1):61-69, 1978. Preliminary version in the 16^th Annual Symposium on Foundations of Computer Science (FOCS 1975). URL: https://epubs.siam.org/doi/abs/10.1137/0207004?journalCode=smjcat.
  32. Richard J Lipton. Straight-line complexity and integer factorization. In International Algorithmic Number Theory Symposium (ANTS 94), pages 71-79. Springer, 1994. URL: https://doi.org/10.1007/3-540-58691-1_45.
  33. Richard J Lipton and Larry J Stockmeyer. Evaluation of polynomials with super-preconditioning. Journal of Computer and System Sciences, 16(2):124-139, 1978. URL: https://www.sciencedirect.com/science/article/pii/0022000078900417.
  34. Meena Mahajan. Algebraic Complexity Classes. In Perspectives in Computational Complexity, pages 51-75. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-05446-9_4.
  35. Carlos Moreira. On asymptotic estimates for arithmetic cost functions. Proceedings of the American Mathematical Society, 125(2):347-353, 1997. URL: https://www.jstor.org/stable/2161660.
  36. Ketan D Mulmuley. The GCT program toward the P vs. NP problem. Communications of the ACM, 55(6):98-107, 2012. URL: https://doi.org/10.1145/2184319.2184341.
  37. Danny Nguyen and Igor Pak. Complexity of short generating functions. In Forum of Mathematics, Sigma, volume 6. Cambridge University Press, 2018. URL: http://arxiv.org/abs/1702.08660.
  38. Øystein Ore. Über höhere kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. Google Scholar
  39. Igor Pak. Complexity problems in enumerative combinatorics. In Proceedings of the International Congress of Mathematicians - Rio de Janeiro 2018. Vol. IV. Invited lectures, pages 3153-3180. World Sci. Publ., Hackensack, NJ, 2018. URL: https://doi.org/10.1142/9789813272880_0176.
  40. David A Plaisted. New NP-hard and NP-complete polynomial and integer divisibility problems. Theoretical Computer Science, 31(1-2):125-138, 1984. Preliminary in the 17^th Annual Symposium on Foundations of Computer Science (FOCS 1976). URL: https://www.sciencedirect.com/science/article/pii/0304397584901300.
  41. Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  42. Adi Shamir. Factoring numbers in O (logn) arithmetic steps. Information Processing Letters, 8(1):28-31, 1979. URL: https://www.sciencedirect.com/science/article/abs/pii/0020019079900875.
  43. Amir Shpilka and Amir Yehudayoff. Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trendsregistered in Theoretical Computer Science, 5(3-4):207-388, 2010. URL: https://doi.org/10.1561/0400000039.
  44. Michael Shub and Steve Smale. On the intractability of Hilbert’s Nullstellensatz and an algebraic version of "NP ̸ = P?". Duke Math. J., 81(1):47-54 (1996), 1995. A celebration of John F. Nash, Jr. URL: https://doi.org/10.1215/S0012-7094-95-08105-8.
  45. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. Google Scholar
  46. L Valiant. Reducibility by algebraic projections in: Logic and algorithmic. In Symposium in honour of Ernst Specker, pages 365-380, 1982. Google Scholar
  47. Leslie G Valiant. Completeness classes in algebra. In Proceedings of the 11th Annual ACM symposium on Theory of computing, pages 249-261. ACM, 1979. URL: https://doi.org/10.1145/800135.804419.
  48. Joachim Von Zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013. Google Scholar
  49. Wact. Some Accessible Open Problems. Workshop on Algebraic Complexity Theory (WACT 2016). URL: https://www.cs.tau.ac.il/~shpilka/wact2016/concreteOpenProblems/openprobs.pdf.
  50. Klaus W Wagner. The complexity of combinatorial problems with succinct input representation. Acta informatica, 23(3):325-356, 1986. URL: https://doi.org/10.1007/BF00289117.
  51. Richard Zippel. Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM '79, pages 216-226, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
  52. J.von zur Gathen and V. Strassen. Some polynomials that are hard to compute. Theoretical Computer Science, 11(3):331-335, 1980. URL: http://www.sciencedirect.com/science/article/pii/0304397580900201.
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