Abstract
Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. The transcendence degree (trdeg) of a set \(\{f_1, \dotsc, f_m\} \subset \mathbb{F}[x_1, \dotsc, x_n]\) of polynomials is the maximal size r of an algebraically independent subset. In this paper we design blackbox and efficient linear maps ϕ that reduce the number of variables from n to r but maintain trdeg{ϕ(f i )} i = r, assuming f i ’s sparse and small r. We apply these fundamental maps to solve several cases of blackbox identity testing:
-
1
Given a circuit C and sparse subcircuits f 1,…,f m of trdeg r such that D: = C(f 1,…,f m ) has polynomial degree, we can test blackbox D for zeroness in poly(size(D))r time.
-
2
Define a ΣΠΣΠ δ (k,s,n) circuit C to be of the form ∑ i = 1 k ∏ j = 1 s f i,j , where f i,j are sparse n-variate polynomials of degree at most δ. For k = 2, we give a \(poly(\delta sn)^{\delta^2}\) time blackbox identity test.
-
3
For a general depth-4 circuit we define a notion of rank. Assuming there is a rank bound R for minimal simple ΣΠΣΠ δ (k,s,n) identities, we give a \(poly(\delta snR)^{Rk\delta^2}\) time blackbox identity test for ΣΠΣΠ δ (k,s,n) circuits. This partially generalizes the state of the art of depth-3 to depth-4 circuits.
The notion of trdeg works best with large or zero characteristic, but we also give versions of our results for arbitrary fields.
The first two authors are grateful to the Bonn International Graduate School in Mathematics for research funding.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.M., Lenstra, H.W.: Finding irreducible polynomials over finite fields. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pp. 350–355 (1986)
Agrawal, M.: Proving lower bounds via pseudo-random generators. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 92–105. Springer, Heidelberg (2005)
Agrawal, M.: Determinant versus permanent. In: Proceedings of the 25th International Congress of Mathematicians (ICM), vol. 3, pp. 985–997 (2006)
Agrawal, M., Biswas, S.: Primality and identity testing via Chinese remaindering. Journal of the ACM 50(4), 429–443 (2003)
Agrawal, M., Vinay, V.: Arithmetic circuits: A chasm at depth four. In: Proceedings of the 49th Annual Symposium on Foundations of Computer Science (FOCS), pp. 67–75 (2008)
Anderson, M., van Melkebeek, D., Volkovich, I.: Derandomizing polynomial identity testing for multilinear constant-read formulae. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC (2011)
Beecken, M., Mittmann, J., Saxena, N.: Algebraic Independence and Blackbox Identity Testing. Tech. Rep. TR11-022, Electronic Colloquium on Computational Complexity, ECCC (2011)
Chen, Z., Kao, M.: Reducing randomness via irrational numbers. SIAM J. on Computing 29(4), 1247–1256 (2000)
DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193–195 (1978)
Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. Computational Complexity 18(1), 1–58 (2009)
Dvir, Z., Gutfreund, D., Rothblum, G., Vadhan, S.: On approximating the entropy of polynomial mappings. In: Proceedings of the 2nd Symposium on Innovations in Computer Science, ICS (2011)
Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Springer, New York (1995)
Heintz, J., Schnorr, C.P.: Testing polynomials which are easy to compute (extended abstract). In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 262–272 (1980)
Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1), 1–46 (2004)
Kalorkoti, K.: A lower bound for the formula size of rational functions. SIAM J. Comp. 14(3), 678–687 (1985)
Karnin, Z., Shpilka, A.: Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in. In: Proceedings of the 23rd Annual Conference on Computational Complexity (CCC), pp. 280–291 (2008)
Kayal, N.: The Complexity of the Annihilating Polynomial. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pp. 184–193 (2009)
Kemper, G.: A Course in Commutative Algebra. Springer, Berlin (2011)
Lewin, D., Vadhan, S.: Checking polynomial identities over any field: Towards a derandomization? In: Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC), pp. 428–437 (1998)
Lovász, L.: On determinants, matchings and random algorithms. In: Fundamentals of Computation Theory (FCT), pp. 565–574 (1979)
Lovász, L.: Singular spaces of matrices and their applications in combinatorics. Bol. Soc. Braz. Mat. 20, 87–99 (1989)
Perron, O.: Algebra I (Die Grundlagen). Berlin (1927)
Płoski, A.: Algebraic Dependence of Polynomials After O. Perron and Some Applications. In: Cojocaru, S., Pfister, G., Ufnarovski, V. (eds.) Computational Commutative and Non-Commutative Algebraic Geometry, pp. 167–173. IOS Press, Amsterdam (2005)
Saraf, S., Volkovich, I.: Black-box identity testing of depth-4 multilinear circuits. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC (2011)
Saxena, N., Seshadhri, C.: From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pp. 21–29 (2010)
Saxena, N., Seshadhri, C.: An Almost Optimal Rank Bound for Depth-3 Identities. SIAM J. Comp. 40(1), 200–224 (2011)
Saxena, N., Seshadhri, C.: Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn’t matter. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC (2011)
Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27(4), 701–717 (1980)
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)
Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol. 72, pp. 216–226. Springer, Heidelberg (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beecken, M., Mittmann, J., Saxena, N. (2011). Algebraic Independence and Blackbox Identity Testing. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6756. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22012-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-22012-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22011-1
Online ISBN: 978-3-642-22012-8
eBook Packages: Computer ScienceComputer Science (R0)