Abstract
The motivation for this work (Pandey et al. 2016) comes from two problems: testing algebraic independence of arithmetic circuits over a field of small characteristic and generalizing 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\({^{\#{\rm P}}}\) (Mittmann, Saxena, Scheiblechner, Trans.AMS’14). Currently, even the case of two bivariate circuits over \({\mathbb{F}_2}\) is open. We come up with a natural generalization of Jacobian criterion that works over all characteristics. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step toward 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 characteristics. 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. M. Adleman & H. W. Lenstra (1986). Finding irreducible polynomials over finite fields. In STOC, 350–355
Manindra Agrawal, Sumanta Ghosh & Nitin Saxena (2017). Bootstrapping variables in algebraic circuits. Technical report, https://www.cse.iitk.ac.in/users/nitin/research.html. (To appear in 50th ACM Symposium on Theory of Computing (STOC), 2018)
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi & Nitin Saxena (2016). Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits. SIAM J. Comput. 45(4), 1533–1562. (Special issue for STOC 2011)
Manindra Agrawal, Chandan Saha & Nitin Saxena (2013). Quasi-polynomial hitting-set for set-depth-\(\Delta \) formulas. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, 321–330. ACM
Manindra Agrawal & V. Vinay (2008). Arithmetic Circuits: A Chasm at Depth Four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 67–75
Bauer, W., Strassen, V.: The complexity of partial derivatives. Theoretical Computer Science 22(3), 317–330 (1983)
M. Beecken, J. Mittmann & N. Saxena (2013). Algebraic Independence and Blackbox Identity Testing. Inf. Comput. 222, 2–19. (Special issue for ICALP 2011)
Dario A Bini & Victor Pan (2012). Polynomial and matrix computations: fundamental algorithms. Springer Science & Business Media
Nicolas Bourbaki (2013). Algebra II: Chapters 4-7. Springer Science & Business Media
Peter Bürgisser, Michael Clausen & Amin Shokrollahi (2013). Algebraic complexity theory, volume 315. Springer Science & Business Media
David A Cox, John Little & Donal O’Shea (2007). Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics
Laszlo Csanky (1976). Fast parallel matrix inversion algorithms. SIAM Journal on Computing 5(4), 618–623. (Conference version in FOCS 1975)
Radu Curticapean (2013). Counting Matchings of Size k Is #W[1]-Hard. In Automata, Languages, and Programming, 352–363. Springer
DeMillo, Richard A., Lipton, Richard J.: A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193–195 (1978)
Pranjal Dutta, Nitin Saxena & Amit Sinhababu (2017). Discovering the roots: Uniform closure results for algebraic classes under factoring. Technical report, https://www.cse.iitk.ac.in/users/nitin/research.html. (To appear in 50th ACM Symposium on Theory of Computing (STOC), 2018)
Z. Dvir, A. Gabizon & A. Wigderson (2009a). Extractors and rank extractors for polynomial sources. Comput. Complex. 18(1), 1–58. (Conference version in FOCS 2007)
Z. Dvir, D. Gutfreund, G.N. Rothblum & S.P. Vadhan (2011). On Approximating the Entropy of Polynomial Mappings. In Innovations in Computer Science (ICS), 460–475
Zeev Dvir (2009). Extractors for Varieties. In Proceedings of the 24th IEEE Conference on Computational Complexity (CCC), 102–113
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf & Madhu Sudan (2013). Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM Journal on Computing 42(6), 2305–2328. (Conference version in FOCS 2009)
Zeev Dvir, Amir Shpilka & Amir Yehudayoff (2009b). Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing 39(4), 1279–1293. (Conference version in STOC 2008)
Richard Ehrenborg & Gian-Carlo Rota: Apolarity and canonical forms for homogeneous polynomials. European Journal of Combinatorics 14(3), 157–181 (1993)
Michael A Forbes (2014). Polynomial identity testing of read-once oblivious algebraic branching programs. Ph.D. thesis, Massachusetts Institute of Technology
Michael A Forbes (2015). Deterministic divisibility testing via shifted partial derivatives. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, 451–465. IEEE
Krister Forsman (1992). Two Themes in Commutative Algebra: Algebraic Dependence and Kähler Differentials
Keith O Geddes, Stephen R Czapor & George Labahn (1992). Algorithms for computer algebra. Springer Science & Business Media
Guo, Zeyu, Saxena, Nitin, Sinhababu, Amit: Algebraic dependencies and PSPACE algorithms in approximative complexity. Electronic Colloquium on Computational Complexity (ECCC) 25, 19 (2018). (To appear in Computational Complexity Conference (CCC), 2018).
Gupta, Ankit, Kamath, Pritish, Kayal, Neeraj, Saptharishi, Ramprasad: Arithmetic Circuits: A Chasm at Depth Three. 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26–29 October, 2013, pp. 578–587. CA, USA, Berkeley (2013)
Hasse, Helmut, Schmidt, Friedrich K.: 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)
L. Illusie (1994). Crystalline cohomology. In Proc. Sympos. Pure Math., volume 55, 43–70. Motives (Seattle, WA, 1991)
I Martin Isaacs (1994). Algebra: a graduate course, volume 100. American Mathematical Soc
Jacobi, C.G.J.: De determinantibus functionalibus. J. Reine Angew. Math. 22(4), 319–359 (1841)
Nathan Jacobson (2012). Lectures in Abstract Algebra: III. Theory of Fields and Galois Theory, volume 32. Springer Science & Business Media
K. A. Kalorkoti (1985). A Lower Bound for the Formula Size of Rational Functions. SIAM J. Comp. 14(3), 678–687. (Conference version in ICALP 1982)
Erich Kaltofen (1987). Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, 443–452. ACM
Kaltofen, Erich: Factorization of polynomials given by straight-line programs. Randomness and Computation 5, 375–412 (1989)
Erich Kaltofen (2003). Polynomial factorization: a success story. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (ISSAC’03), 3–4. ACM
Kaltofen, Erich, Trager, Barry M.: Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation 9(3), 301–320 (1990)
N. Kayal (2009). The Complexity of the Annihilating Polynomial. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), 184–193
Neeraj Kayal, Nutan Limaye, Chandan Saha & Srikanth Srinivasan (2014a). An exponential lower bound for homogeneous depth four arithmetic formulas. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, 61–70. IEEE
Neeraj Kayal, Chandan Saha & Ramprasad Saptharishi (2014b). A super-polynomial lower bound for regular arithmetic formulas. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 146–153. ACM
Gregor Kemper (2010). A course in Commutative Algebra, volume 256. Springer Science & Business Media
Anthony W Knapp (2007). Advanced algebra. Springer Science & Business Media
N. Koblitz (1984). P-adic Numbers, P-adic Analysis, and Zeta-Functions. Springer-Verlag, 2nd edition
Steven G Krantz & Harold R Parks (2012). The implicit function theorem: history, theory, and applications. Springer Science & Business Media
Martin Kreuzer & Lorenzo Robbiano (2005). Computational commutative algebra 2. Springer Science & Business Media
Mrinal Kumar & Shubhangi Saraf (2016). Arithmetic Circuits with Locally Low Algebraic Rank. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, 34:1–34:27
Mrinal Kumar & Shubhangi Saraf (2017). On the Power of Homogeneous Depth 4 Arithmetic Circuits. SIAM J. Comput. 46(1), 336–387. (Conference version in FOCS 2014)
Lindström, Bernt: On the algebraic characteristic set for a class of matroids. Proceedings of the American Mathematical Society 95(1), 147–151 (1985)
M.S. L’vov, : Calculation of invariants of programs interpreted over an integrality domain. Cybernetics and Systems Analysis 20, 492–499 (1984)
Johannes Mittmann (2013). Independence in Algebraic Complexity Theory. Ph.D. thesis, Universitäts-und Landesbibliothek Bonn
Mittmann, Johannes, Saxena, Nitin, Scheiblechner, Peter: Algebraic independence in positive characteristic: A \(p\)-adic calculus. Transactions of the American Mathematical Society 366(7), 3425–3450 (2014)
Rafael Oliveira (2016). Factors of low individual degree polynomials. Computational Complexity 25(2), 507–561. (Special issue for CCC 2015)
James G Oxley (2006). Matroid theory, volume 3. Oxford university press
Anurag Pandey, Nitin Saxena & Amit Sinhababu (2016). 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: August 22–26, 2016 - Kraków. Poland 74(1–74), 15 (2016)
Perron, O.: Algebra I (Die Grundlagen). W. de Gruyter, Berlin (1927)
A. Płoski (2005). Algebraic Dependence of Polynomials After O. Perron and Some Applications. In Computational Commutative and Non-Commutative Algebraic Geometry, 167–173. IOS press
Ran Raz (2008). Elusive functions and lower bounds for arithmetic circuits. In Proceedings of the fortieth annual ACM symposium on Theory of computing, 711–720. ACM
Ramprasad Saptharishi (2016). A survey of lower bounds in arithmetic circuit complexity. https://github.com/dasarpmar/lowerbounds-survey/
Nitin Saxena (2014). Progress on polynomial identity testing-II. In Perspectives in Computational Complexity, 131–146. Springer
Schwartz, J.T.: Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM 27(4), 701–717 (1980)
David Shannon & Moss Sweedler: Using Gröbner bases to determine algebra membership, split surjective algebra homomorphisms determine birational equivalence. Journal of Symbolic Computation 6(2–3), 267–273 (1988)
Shpilka, A., Yehudayoff, A.: Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3–4), 207–388 (2010)
Volker Strassen (1973). Vermeidung von Divisionen. Journal für die reine und angewandte Mathematik 264, 184–202. URL http://eudml.org/doc/151394
Teichmüller, Oswald: Differentialrechnung bei Charakteristik p. Journal für die reine und angewandte Mathematik 175, 89–99 (1936)
William Nathaniel Traves (1998). Differential operators and Nakai’s conjecture. Ph.D. thesis, National Library of Canada= Bibliothèque nationale du Canada
Joachim Von Zur Gathen & Jürgen Gerhard (2013). Modern computer algebra. Cambridge university press
Richard Zippel (1979). Probabilistic algorithms for sparse polynomials. Springer
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pandey, A., Saxena, N. & Sinhababu, A. Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. comput. complex. 27, 617–670 (2018). https://doi.org/10.1007/s00037-018-0167-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-018-0167-5
Keywords
- independence
- transcendence
- finite field
- Hasse–Schmidt
- Jacobian
- differential
- inseparable
- degree
- circuit
- identity testing
- lower bound
- depth-4
- shifted partials