Document Open Access Logo

Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits

Authors Anurag Pandey, Nitin Saxena, Amit Sinhababu

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.74.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Anurag Pandey
Nitin Saxena
Amit Sinhababu

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.74

Abstract

The motivation for this work comes from two problems--test algebraic independence of arithmetic circuits over a field of small characteristic, and generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields. 
 
It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying  inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07).
  
In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as ``functional dependence'' in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for  arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones  known before.
  
Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a ``good'' transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the ``degree'' of approximation needed in the criterion. To get the locally low algebraic rank circuit applications we follow the known shifted partial derivative based methods.

Subject Classification

Keywords
  • independence
  • transcendence
  • finite field
  • Hasse-Schmidt
  • Jacobian
  • differential
  • inseparable
  • circuit
  • identity testing
  • lower bound
  • depth-4
  • shifte

Metrics

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

References

  1. 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
  2. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 67-75, 2008. Google Scholar
  3. W. Bauer and V. Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22(3):317-330, 1983. Google Scholar
  4. 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
  5. Radu Curticapean. Counting matchings of size k is #W[1]-hard. In Automata, Languages, and Programming, pages 352-363. Springer, 2013. Google Scholar
  6. Richard A DeMillo and Richard J Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  7. 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
  8. Z. Dvir, D. Gutfreund, G.N. Rothblum, and S.P. Vadhan. On approximating the entropy of polynomial mappings. In Innovations in Computer Science (ICS), pages 460-475, 2011. Google Scholar
  9. Zeev Dvir. Extractors for varieties. In Proceedings of the 24th IEEE Conference on Computational Complexity (CCC), pages 102-113, 2009. Google Scholar
  10. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. SIAM Journal on Computing, 42(6):2305-2328, 2013. (Preliminary version in FOCS'09). Google Scholar
  11. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing, 39(4):1279-1293, 2009. Google Scholar
  12. Richard Ehrenborg and Gian-Carlo Rota. Apolarity and canonical forms for homogeneous polynomials. European Journal of Combinatorics, 14(3):157-181, 1993. Google Scholar
  13. Michael A Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs. PhD thesis, Massachusetts Institute of Technology, 2014. Google Scholar
  14. Michael A Forbes. Deterministic divisibility testing via shifted partial derivatives. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 451-465. IEEE, 2015. Google Scholar
  15. Krister Forsman. Two themes in commutative algebra: Algebraic dependence and kähler differentials, 1992. Google Scholar
  16. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 578-587, 2013. Google Scholar
  17. Helmut Hasse and Friedrich K. Schmidt. Noch eine begründung der theorie der höheren differentialquotienten in einem algebraischen funktionenkörper einer unbestimmten. (nach einer brieflichen mitteilung von f.k.schmidt in jena). Journal für die reine und angewandte Mathematik, 177:215-223, 1937. Google Scholar
  18. L. Illusie. Crystalline cohomology. In Proc. Sympos. Pure Math., volume 55, pages 43-70, 1994. Motives (Seattle, WA, 1991). Google Scholar
  19. I Martin Isaacs. Algebra: a graduate course, volume 100. American Mathematical Soc., 1994. Google Scholar
  20. C. G. J. Jacobi. De determinantibus functionalibus. J. Reine Angew. Math., 22(4):319-359, 1841. Google Scholar
  21. K. A. Kalorkoti. A Lower Bound for the Formula Size of Rational Functions. SIAM J. Comp., 14(3):678-687, 1985. (Conference version in ICALP 1982). 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, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 61-70. IEEE, 2014. Google Scholar
  24. Anthony W Knapp. Advanced algebra. Springer Science &Business Media, 2007. Google Scholar
  25. Steven G Krantz and Harold R Parks. The implicit function theorem: history, theory, and applications. Springer Science &Business Media, 2012. Google Scholar
  26. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 364-373. IEEE, 2014. Google Scholar
  27. Mrinal Kumar and Shubhangi Saraf. Arithmetic circuits with locally low algebraic rank. Electronic Colloquium on Computational Complexity (ECCC), 22:194, 2015. (To appear in CCC 2016). URL: http://eccc.hpi-web.de/report/2015/194.
  28. M.S. L'vov. Calculation of invariants of programs interpreted over an integrality domain. Cybernetics and Systems Analysis, 20:492-499, 1984. Google Scholar
  29. 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
  30. James G Oxley. Matroid theory, volume 3. Oxford university press, 2006. Google Scholar
  31. O. Perron. Algebra I (Die Grundlagen). W. de Gruyter, Berlin, 1927. Google Scholar
  32. A. Płoski. Algebraic Dependence of Polynomials After O. Perron and Some Applications. In Computational Commutative and Non-Commutative Algebraic Geometry, pages 167-173. 2005. Google Scholar
  33. 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
  34. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity, 2016. https://github.com/dasarpmar/lowerbounds-survey/. Google Scholar
  35. Nitin Saxena. Progress on polynomial identity testing-ii. In Perspectives in Computational Complexity, pages 131-146. Springer, 2014. Google Scholar
  36. J.T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  37. A. Shpilka and A. 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
  38. Oswald Teichmüller. Differentialrechnung bei charakteristik p. Journal für die reine und angewandte Mathematik, 175:89-99, 1936. Google Scholar
  39. William Nathaniel Traves. Differential operators and Nakai’s conjecture, 1998. Google Scholar
  40. Richard Zippel. Probabilistic algorithms for sparse polynomials. Springer, 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