Document Open Access Logo

Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity

Authors Zeyu Guo, Nitin Saxena, Amit Sinhababu

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.10.pdf
  • Filesize: 0.57 MB
  • 21 pages

Document Identifiers

Author Details

Zeyu Guo
  • Department of Computer Science & Engineering, Indian Institute of Technology Kanpur
Nitin Saxena
  • Department of Computer Science & Engineering, Indian Institute of Technology Kanpur
Amit Sinhababu
  • Department of Computer Science & Engineering, Indian Institute of Technology Kanpur

Funding

  • Guo, Zeyu: Z.G. is funded by DST and Research I Foundation of CSE, IITK.
  • Saxena, Nitin: N.S. thanks the funding support from DST (DST/SJF/MSA-01/2013-14).
  • Sinhababu, Amit: A.S. thanks the travel fund support from Indian Association for Research in Computing Science and ACM India.

Cite As Get BibTex

Zeyu Guo, Nitin Saxena, and Amit Sinhababu. Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CCC.2018.10

Abstract

Testing whether a set f of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). Previously, the best complexity known was NP^{#P} (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). In this work we put the problem in AM cap coAM. In particular, dependence testing is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, eg. graph isomorphism & integer factoring. Our proof method is algebro-geometric- estimating the size of the image/preimage of the polynomial map f over the finite field. A gap in this size is utilized in the AM protocols.
Next, we study the open question of testing whether every annihilator of f has zero constant term (Kayal, CCC'09). We give a geometric characterization using Zariski closure of the image of f; introducing a new problem called approximate polynomials satisfiability (APS). We show that APS is NP-hard and, using projective algebraic-geometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Gröbner basis computation). As an unexpected application of this to approximative complexity theory we get- over any field, hitting-sets for overline{VP} can be verified in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Complexity classes
  • Mathematics of computing → Computations on polynomials
  • Mathematics of computing → Computations in finite fields
Keywords
  • algebraic dependence
  • Jacobian
  • Arthur-Merlin
  • approximate polynomial
  • satisfiability
  • hitting-set
  • border VP
  • finite field
  • PSPACE
  • EXPSPACE
  • GCT Chasm

Metrics

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

References

  1. L. M. Adleman and H. W. Lenstra. Finding irreducible polynomials over finite fields. In STOC, pages 350-355, 1986. Google Scholar
  2. M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena. Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), pages 599-614, 2012. (In SICOMP special issue). Google Scholar
  3. Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena. Bootstrapping variables in algebraic circuits, 2017. (To appear in 50th ACM Symposium on Theory of Computing (STOC), 2018). URL: https://www.cse.iitk.ac.in/users/nitin/research.html.
  4. S. Arora and B. Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  5. László Babai. Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 421-429. ACM, 1985. Google Scholar
  6. M. Beecken, J. Mittmann, and N. Saxena. Algebraic Independence and Blackbox Identity Testing. Inf. Comput., 222:2-19, 2013. (Conference version in ICALP 2011). Google Scholar
  7. Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On algebraic branching programs of small width. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 20:1-20:31, 2017. Google Scholar
  8. Peter Bürgisser. The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics, 4(4):369-396, 2004. (Preliminary version in FOCS 2001). Google Scholar
  9. Peter Bürgisser, Michael Clausen, and Amin Shokrollahi. Algebraic complexity theory, volume 315. Springer Science &Business Media, 2013. Google Scholar
  10. Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. 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 24:1-24:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.24.
  11. Laszlo Csanky. Fast parallel matrix inversion algorithms. SIAM Journal on Computing, 5(4):618-623, 1976. (Conference version in FOCS 1975). Google Scholar
  12. Harm Derksen and Gregor Kemper. Computational invariant theory. Springer, 2015. Google Scholar
  13. Z. Dvir, A. Gabizon, and A. Wigderson. Extractors and rank extractors for polynomial sources. Comput. Complex., 18(1):1-58, 2009. (Conference version in FOCS 2007). Google Scholar
  14. Zeev Dvir. Extractors for varieties. In Proceedings of the 24th IEEE Conference on Computational Complexity (CCC), pages 102-113, 2009. Google Scholar
  15. Richard Ehrenborg and Gian-Carlo Rota. Apolarity and canonical forms for homogeneous polynomials. European Journal of Combinatorics, 14(3):157-181, 1993. Google Scholar
  16. Michael A. Forbes and Amir Shpilka. A PSPACE construction of a hitting set for the closure of small algebraic circuits. Electronic Colloquium on Computational Complexity (ECCC), 24:163, 2017. (To appear in 50th ACM Symposium on Theory of Computing (STOC), 2018). Google Scholar
  17. Joe Harris. Algebraic Geometry: A First Course. Springer, 1992. Google Scholar
  18. Robin Hartshorne. Algebraic geometry, volume 52. Springer Science &Business Media, 2013. Google Scholar
  19. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 262-272. ACM, 1980. Google Scholar
  20. Aubrey W Ingleton. Representation of matroids. Combinatorial mathematics and its applications, 23, 1971. Google Scholar
  21. C. G. J. Jacobi. De determinantibus functionalibus. J. Reine Angew. Math., 22(4):319-359, 1841. Google Scholar
  22. N. Kayal. The Complexity of the Annihilating Polynomial. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pages 184-193, 2009. Google Scholar
  23. Neeraj Kayal and Nitin Saxena. Complexity of ring morphism problems. computational complexity, 15(4):342-390, 2006. Google Scholar
  24. Pascal Koiran. Hilbert’s Nullstellensatz is in the polynomial hierarchy. Journal of complexity, 12(4):273-286, 1996. Google Scholar
  25. János Kollár. Sharp effective Nullstellensatz. Journal of the American Mathematical Society, 1(4):963-975, 1988. Google Scholar
  26. Mrinal Kumar and Shubhangi Saraf. Arithmetic circuits with locally low algebraic rank. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 34:1-34:27, 2016. Google Scholar
  27. Joseph M Landsberg. Tensors: geometry and applications, volume 128. American Mathematical Society Providence, RI, 2012. Google Scholar
  28. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303. ACM, 2014. Google Scholar
  29. Thomas Lehmkuhl and Thomas Lickteig. On the order of approximation in approximative triadic decompositions of tensors. Theoretical Computer Science, 66(1):1-14, 1989. Google Scholar
  30. Ernst W Mayr and Albert R Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in mathematics, 46(3):305-329, 1982. Google Scholar
  31. Johannes Mittmann, Nitin Saxena, and Peter Scheiblechner. Algebraic independence in positive characteristic: A p-adic calculus. Transactions of the American Mathematical Society, 366(7):3425-3450, 2014. Google Scholar
  32. Ketan Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society, 30(1):225-309, 2017. Google Scholar
  33. Ketan D. Mulmuley. Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. In FOCS, pages 629-638, 2012. Google Scholar
  34. Anurag Pandey, Nitin Saxena, and Amit Sinhababu. Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 74:1-74:15, 2016. (In print, Computational Complexity, 2018). Google Scholar
  35. O. Perron. Algebra I (Die Grundlagen). W. de Gruyter, Berlin, 1927. Google Scholar
  36. Arkadiusz Płoski. Algebraic dependence of polynomials after o. perron and some applications. Computational Commutative and Non-Commutative Algebraic Geometry, pages 167-173, 2005. Google Scholar
  37. Ran Raz. Elusive functions and lower bounds for arithmetic circuits. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 711-720. ACM, 2008. Google Scholar
  38. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 99:49-79, 2009. Google Scholar
  39. Nitin Saxena. Progress on polynomial identity testing - II. Electronic Colloquium on Computational Complexity (ECCC), 20:186, 2013. URL: http://eccc.hpi-web.de/report/2013/186.
  40. Marcus Schaefer and Daniel Štefankovič. The complexity of tensor rank. Theory of Computing Systems, Aug 2017. URL: http://dx.doi.org/10.1007/s00224-017-9800-y.
  41. Joachim Schmid. On the affine Bezout inequality. manuscripta mathematica, 88(1):225-232, 1995. Google Scholar
  42. J.T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  43. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. 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