Document Open Access Logo

If VNP Is Hard, Then so Are Equations for It

Authors Mrinal Kumar, C. Ramya , Ramprasad Saptharishi , Anamay Tengse

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.44.pdf
  • Filesize: 0.78 MB
  • 13 pages

Document Identifiers

Author Details

Mrinal Kumar
  • Indian Institute of Technology Bombay, India
C. Ramya
  • Chennai Mathematical Institute, India
Ramprasad Saptharishi
  • School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India
Anamay Tengse
  • Department of Computer Science, University of Haifa, Israel

Funding

  • Ramya, C.: Research supported by INSPIRE Faculty Fellowship of DST and by a grant from the Infosys Foundation. Part of this work was done when at the Tata Institute of Fundamental Research, Mumbai, India (DAE project 12-R&D-TFR-5.01-0500).
  • Saptharishi, Ramprasad: Research was supported by the Department of Atomic Energy, Government of India, under project no. 12-R&D-TFR-5.01-0500, and also the SERB Ramanujan Fellowship.
  • Tengse, Anamay: Research supported by the Israel Science Foundation (grant No. 716/20). Part of this work was done when at the Tata Institute of Fundamental Research, Mumbai, India, as a student (DAE project no. 12-R&D-TFR-5.01-0500), and later as a visitor (Prof. Prahladh Harsha’s Swarnajaynti fellowship and Prof. Arkadev Chattopadhyay’s Microsoft Research funds).

Acknowledgements

We thank anonymous reviewers of an earlier version of this paper and Joshua Grochow, whose questions pointed us in the direction of this result. We also thank the reviewers of STACS 2022 for their helpful comments and suggestions. We also thank Prerona Chatterjee and Ben Lee Volk for helpful discussions at various stages of this work.

Cite AsGet BibTex

Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.44

Abstract

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee, Kumar, Ramya, Saptharishi and Tengse (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Computational Complexity
  • Algebraic Circuits
  • Algebraic Natural Proofs

Metrics

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

Related Versions

References

  1. Scott Aaranson and Andrew Drucker. Arithmetic natural proofs theory is sought. Shtetl Optimized: Scott Aaranson’s Blog, 2008. URL: https://www.scottaaronson.com/blog/?p=336.
  2. Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Generalized matrix completion and algebraic natural proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1193-1206, 2018. URL: https://doi.org/10.1145/3188745.3188832.
  3. Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer. Variety membership testing, algebraic natural proofs, and geometric complexity theory. CoRR, abs/1911.02534, 2019. URL: http://arxiv.org/abs/1911.02534.
  4. Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. On the existence of algebraically natural proofs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 870-880. IEEE, 2020. http://arxiv.org/abs/2004.14147, URL: https://doi.org/10.1109/FOCS46700.2020.00085.
  5. Richard A. DeMillo and Richard J. Lipton. A Probabilistic Remark on Algebraic Program Testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
  6. Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 1:1-1:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.1.
  7. Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Theory of Computing, 14(1):1-45, 2018. URL: https://doi.org/10.4086/toc.2018.v014a018.
  8. Ankit Garg, Visu Makam, Rafael Oliveira, and Avi Wigderson. More barriers for rank methods, via a "numeric to symbolic" transfer. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 824-844. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00054.
  9. Joshua A. Grochow. Unifying known lower bounds via geometric complexity theory. Computational Complexity, 24(2):393-475, 2015. URL: https://doi.org/10.1007/s00037-015-0103-x.
  10. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs/1701.01717, 2017. URL: http://arxiv.org/abs/1701.01717.
  11. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  12. Mrinal Kumar and Ben Lee Volk. A polynomial degree bound on equations for non-rigid matrices and small linear circuits. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 9:1-9:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.9.
  13. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. Electron. Colloquium Comput. Complex., page 81, 2021. URL: https://eccc.weizmann.ac.il/report/2021/081.
  14. Øystein Ore. Über höhere kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. Google Scholar
  15. Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
  16. Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  17. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
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