Document Open Access Logo

Polynomial Identity Testing via Evaluation of Rational Functions

Authors Dieter van Melkebeek, Andrew Morgan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.119.pdf
  • Filesize: 0.67 MB
  • 24 pages

Document Identifiers

Author Details

Dieter van Melkebeek
  • University of Wisconsin-Madison, Madison, WI, USA
Andrew Morgan
  • University of Wisconsin-Madison, Madison, WI, USA

Funding

Research partially supported by the US National Science Foundation through grant CCF-1838434.

Acknowledgements

We are indebted to Gautam Prakriya for helpful discussions and detailed feedback. We also thank Amir Shpilka for helpful comments and suggestions, as well as Ilya Volkovich and the anonymous reviewers. We are grateful to Hervé Fournier and Arpita Korwar for their presentation at WACT'18 in Paris [Fournier and Korwar, 2018].

Cite AsGet BibTex

Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.119

Abstract

We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. In spite of the univariate nature, we establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials in the abscissas. We study the power of the generator by characterizing its vanishing ideal, i.e., the set of polynomials that it fails to hit. Capitalizing on the univariate nature, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition size of set-multi-linearity in the vanishing ideal. Inspired by an alternating algebra representation, we develop a structured deterministic membership test for the vanishing ideal. As a proof of concept we rederive known derandomization results based on the generator by Shpilka and Volkovich, and present a new application for read-once oblivious arithmetic branching programs that provably transcends the usual combinatorial techniques.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Derandomization
  • Gröbner Basis
  • Lower Bounds
  • Polynomial Identity Testing

Metrics

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

References

  1. Manindra Agrawal. Proving lower bounds via pseudo-random generators. In International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 92-105. Springer, 2005. Google Scholar
  2. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669-697, 2015. Google Scholar
  3. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-Δ formulas. In ACM Symposium on Theory of Computing (STOC), pages 321-330, 2013. Google Scholar
  4. Matthew Anderson, Michael A Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity testing and lower bounds for read-k oblivious algebraic branching programs. ACM Transactions on Computation Theory, 10(1):1-30, 2018. Google Scholar
  5. Matthew Anderson, Dieter van Melkebeek, and Ilya Volkovich. Deterministic polynomial identity tests for multilinear bounded-read formulae. Computational Complexity, 24(4):695-776, 2015. Google Scholar
  6. Vishwas Bhargava and Sumanta Ghosh. Improved Hitting Set for Orbit of ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 30:1-30:23, 2021. Google Scholar
  7. David A Cox, John Little, and Donal O'Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2013. Google Scholar
  8. Richard A Demillo and Richard J Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  9. Michael A Forbes. Deterministic divisibility testing via shifted partial derivatives. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 451-465, 2015. Google Scholar
  10. Michael A Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In ACM Symposium on Theory of Computing (STOC), pages 867-875, 2014. Google Scholar
  11. Michael A Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 243-252, 2013. Google Scholar
  12. Michael A Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In ACM SIGACT Symposium on Theory of Computing (STOC), pages 653-664, 2017. Google Scholar
  13. Hervé Fournier and Arpita Korwar. Limitations of the Shpilka-Volkovich generator. Workshop on Algebraic Complexity Theory (WACT), Paris, 2018. Google Scholar
  14. Zeyu Guo and Rohit Gurjar. Improved explicit hitting-sets for ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2020. Google Scholar
  15. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Theory of Computing, 13(2):1-21, 2017. Google Scholar
  16. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Computational Complexity, 26(4):835-880, 2017. Google Scholar
  17. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute. In ACM Symposium on Theory of Computing (STOC), pages 262-272, 1980. Google Scholar
  18. Russell Impagliazzo and Avi Wigderson. P=BPP if E requires exponential circuits: Derandomizing the XOR lemma. In ACM Symposium on Theory of Computing (STOC), pages 220-229, 1997. Google Scholar
  19. Maurice Jansen, Youming Qiao, and Jayalal Sarma M.N. Deterministic Black-Box Identity Testing π-Ordered Algebraic Branching Programs. In IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 8, pages 296-307, 2010. Google Scholar
  20. Maurice Jansen, Youming Qiao, and Jayalal Sarma. Deterministic identity testing of read-once algebraic branching programs. arXiv preprint arXiv:0912.2565, 2009. Google Scholar
  21. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  22. Zohar S Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM Journal on Computing, 42(6):2114, 2013. Google Scholar
  23. Arpita Korwar. Personal communication, February 2021. Google Scholar
  24. Mrinal Kumar and Shubhangi Saraf. Arithmetic circuits with locally low algebraic rank. Theory of Computing, 13(1):1-33, 2017. Google Scholar
  25. Dori Medini and Amir Shpilka. Hitting Sets and Reconstruction for Dense Orbits in VP_e and ΣΠΣ Circuits. In Computational Complexity Conference (CCC), volume 200, pages 19:1-19:27, 2021. Google Scholar
  26. Daniel Minahan and Ilya Volkovich. Complete derandomization of identity testing and reconstruction of read-once formulas. ACM Transactions on Computation Theory (TOCT), 10(3):1-11, 2018. Google Scholar
  27. Noam Nisan. Lower bounds for non-commutative computation. In ACM Symposium on Theory of Computing (STOC), pages 410-418, 1991. Google Scholar
  28. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  29. Øystein Ore. Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. Google Scholar
  30. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. Google Scholar
  31. Chandan Saha and Bhargav Thankey. Hitting Sets for Orbits of Circuit Classes and Polynomial Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 50:1-50:26, 2021. Google Scholar
  32. Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. Google Scholar
  33. Amir Shpilka and Ilya Volkovich. Read-once polynomial identity testing. Computational Complexity, 24(3):477-532, 2015. Google Scholar
  34. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010. Google Scholar
  35. Richard Zippel. Probabilistic algorithms for sparse polynomials. In International symposium on symbolic and algebraic manipulation, 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 Imprint Privacy Contact