Document Open Access Logo

On Solving Sparse Polynomial Factorization Related Problems

Authors Pranav Bisht, Ilya Volkovich

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.10.pdf
  • Filesize: 0.82 MB
  • 22 pages

Document Identifiers

Author Details

Pranav Bisht
  • Computer Science Department, Boston College, Chestnut Hill, MA, USA
Ilya Volkovich
  • Computer Science Department, Boston College, Chestnut Hill, MA, USA

Acknowledgements

The authors would like to thank the anonymous referees for their detailed comments and suggestions on the previous version of the paper.

Cite As Get BibTex

Pranav Bisht and Ilya Volkovich. On Solving Sparse Polynomial Factorization Related Problems. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.10

Abstract

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most s terms and individual degree bounded by d can itself have at most s^O(d²log n) terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. s^poly(d)). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give efficient (deterministic) algorithms for identity testing of Σ^[2]ΠΣΠ^[ind-deg d] circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Sparse Polynomials
  • Identity Testing
  • Derandomization
  • Factor-Sparsity
  • Multivariate Polynomial Factorization

Metrics

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

Related Versions

References

  1. M. Agrawal, S. Ghosh, and N. Saxena. Bootstrapping variables in algebraic circuits. Proceedings of the National Academy of Sciences, 116(17):8107-8118, 2019. Google Scholar
  2. M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 67-75, 2008. Google Scholar
  3. M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pages 301-309, 1988. Google Scholar
  4. V. Bhargava, S. Saraf, and I. Volkovich. Deterministic factorization of sparse polynomials with bounded individual degree. J. ACM, 67(2):8:1-8:28, 2020. Google Scholar
  5. P. Bisht and N. Saxena. Derandomization via symmetric polytopes: Poly-timefactorization of certain sparse polynomials. In Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2022. URL: https://www.cse.iitk.ac.in/users/nitin/papers/symmetricSparse.pdf.
  6. P. Bisht and I. Volkovich. On solving sparse polynomial factorization related problems. Electron. Colloquium Comput. Complex., TR22-070, 2022. URL: https://eccc.weizmann.ac.il/report/2022/070.
  7. B. Chor and R. L. Rivest. A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory, 34(5):901-909, 1988. Google Scholar
  8. D. A. Cox, J. Little, and D. O'Shea. Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4. ed.). Undergraduate texts in mathematics. Springer, 2015. Google Scholar
  9. R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7(4):193-195, 1978. Google Scholar
  10. P. Dutta, P. Dwivedi, and N. Saxena. Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. In 36th Conference on Computational Complexity (CCC 2021), volume 5, page 9, 2021. Google Scholar
  11. M. A. Forbes. Deterministic divisibility testing via shifted partial derivatives. In FOCS, 2015. Google Scholar
  12. J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 1999. Google Scholar
  13. J. von zur Gathen and E. Kaltofen. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences, 31(2):265-287, 1985. URL: https://doi.org/10.1016/0022-0000(85)90044-3.
  14. K. O. Geddes, S. R. Czapor, and G. Labahn. Algorithms for computer algebra. Kluwer, 1992. Google Scholar
  15. E. Grigorescu, K. Jung, and R. Rubinfeld. A local decision test for sparse polynomials. Inf. Process. Lett., 110(20):898-901, 2010. URL: https://doi.org/10.1016/j.ipl.2010.07.012.
  16. V. Guruswami and M. Sudan. Improved decoding of reed-solomon codes and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):1757-1767, 1999. Google Scholar
  17. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  18. E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness in Computation, volume 5 of Advances in Computing Research, pages 375-412. JAI Press Inc., Greenwhich, Connecticut, 1989. Google Scholar
  19. E. Kaltofen and B. M. Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. of Symbolic Computation, 9(3):301-320, 1990. Google Scholar
  20. A. Klivans and D. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 216-223, 2001. Google Scholar
  21. N. Limaye, S. Srinivasan, and S. Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In FOCS 2021, 2022. Google Scholar
  22. S. Peleg and A. Shpilka. Polynomial time deterministic identity testing algorithm for Σ^[3]ΠΣΠ^[2] circuits via edelstein-kelly type theorem for quadratic polynomials. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 259-271, 2021. Google Scholar
  23. C. Saha, R. Saptharishi, and N. Saxena. A case of depth-3 identity testing, sparse factorization and duality. Computational Complexity, 22(1):39-69, 2013. URL: https://doi.org/10.1007/s00037-012-0054-4.
  24. S. Saraf and I. Volkovich. Blackbox identity testing for depth-4 multilinear circuits. Combinatorica, 38(5):1205-1238, 2018. Google Scholar
  25. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  26. A. Shpilka and I. Volkovich. On the relation between polynomial identity testing and finding variable disjoint factors. In Automata, Languages and Programming, 37th International Colloquium (ICALP), pages 408-419, 2010. Full version at URL: https://eccc.weizmann.ac.il/report/2010/036.
  27. V. Strassen. Vermeidung von divisionen. J. of Reine Angew. Math., 264:182-202, 1973. Google Scholar
  28. M. Sudan. Decoding of reed solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180-193, 1997. Google Scholar
  29. I. Volkovich. Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials. In APPROX-RANDOM, pages 943-958, 2015. Google Scholar
  30. I. Volkovich. On some computations on sparse polynomials. In APPROX-RANDOM, pages 48:1-4:21, 2017. Google Scholar
  31. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 216-226, 1979. 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 About DROPS Imprint Privacy Contact