More Web Proxy on the site http://driver.im/

Article

Algebraic independence and blackbox identity testing

Authors:

Johannes Mittmann,

Nitin SaxenaAuthors Info & Claims

ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

Pages 137 - 148

Published: 04 July 2011 Publication History

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₁, ..., f_m} ⊂ F[x₁, ..., 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₁, ..., f_m of trdeg r such that D := C(f₁, ..., 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 (δsn)^δ² 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(δsnR)^Rkδ² 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.

References

[1]

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).

Digital Library

[2]

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).

Digital Library

[3]

Agrawal, M.: Determinant versus permanent. In: Proceedings of the 25th International Congress of Mathematicians (ICM), vol. 3, pp. 985-997 (2006).

[4]

Agrawal, M., Biswas, S.: Primality and identity testing via Chinese remaindering. Journal of the ACM 50(4), 429-443 (2003).

Digital Library

[5]

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).

Digital Library

[6]

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).

Digital Library

[7]

Beecken, M., Mittmann, J., Saxena, N.: Algebraic Independence and Blackbox Identity Testing. Tech. Rep. TR11-022, Electronic Colloquium on Computational Complexity, ECCC (2011).

[8]

Chen, Z., Kao, M.: Reducing randomness via irrational numbers. SIAM J. on Computing 29(4), 1247-1256 (2000).

Digital Library

[9]

DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193-195 (1978).

[10]

Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. Computational Complexity 18(1), 1-58 (2009).

Digital Library

[11]

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).

[12]

Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Springer, New York (1995).

[13]

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).

Digital Library

[14]

Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1), 1-46 (2004).

Digital Library

[15]

Kalorkoti, K.: A lower bound for the formula size of rational functions. SIAM J. Comp. 14(3), 678-687 (1985).

[16]

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).

Digital Library

[17]

Kayal, N.: The Complexity of the Annihilating Polynomial. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pp. 184-193 (2009).

Digital Library

[18]

Kemper, G.: A Course in Commutative Algebra. Springer, Berlin (2011).

[19]

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).

Digital Library

[20]

Lovász, L.: On determinants, matchings and random algorithms. In: Fundamentals of Computation Theory (FCT), pp. 565-574 (1979).

[21]

Lovász, L.: Singular spaces of matrices and their applications in combinatorics. Bol. Soc. Braz. Mat. 20, 87-99 (1989).

[22]

Perron, O.: Algebra I (Die Grundlagen). Berlin (1927).

[23]

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).

[24]

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).

Digital Library

[25]

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).

Digital Library

[26]

Saxena, N., Seshadhri, C.: An Almost Optimal Rank Bound for Depth-3 Identities. SIAM J. Comp. 40(1), 200-224 (2011).

Digital Library

[27]

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).

Digital Library

[28]

Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27(4), 701-717 (1980).

Digital Library

[29]

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).

Digital Library

[30]

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).

Digital Library

Cited By

Minahan DVolkovich I(2018)Complete Derandomization of Identity Testing and Reconstruction of Read-Once FormulasACM Transactions on Computation Theory10.1145/319683610:3(1-11)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3196836
Agrawal MGhosh SSaxena NDiakonikolas IKempe DHenzinger M(2018)Bootstrapping variables in algebraic circuitsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188762(1166-1179)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188762
Minahan DVolkovich I(2017)Complete derandomization of identity testing and reconstruction of read-once formulasProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135627(1-13)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135627
Show More Cited By

Algebraic independence and blackbox identity testing
1. Theory of computation

Recommendations

Algebraic independence and blackbox identity testing

Algebraic independence is a fundamental notion in commutative algebra that generalizes independence of linear polynomials. Polynomials {f"1,...,f"m}@?K[x"1,...,x"n] (over a field K) are called algebraically independent if there is no non-zero polynomial ...
Blackbox Polynomial Identity Testing for Depth 3 Circuits
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed ...
Blackbox identity testing for sum of special ROABPs and its border class
Abstract
We look at the problem of blackbox polynomial identity testing (PIT) for the model of read-once oblivious algebraic branching programs (ROABP), where the number of variables is logarithmic to the input size of ROABP. We restrict width of ROABP to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

July 2011

665 pages

ISBN:9783642220111

Editors:
Luca Aceto
Reykjavik University, School of Computer Science, Reykjavík, Iceland
,
Monika Henzinger
Universität Wien, Fakultät für Informatik, Wien, Österreich
,
Jiří Sgall
Charles University, Department of Applied Mathematics, Praha 1, Czech Republic

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 July 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Minahan DVolkovich I(2018)Complete Derandomization of Identity Testing and Reconstruction of Read-Once FormulasACM Transactions on Computation Theory10.1145/319683610:3(1-11)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3196836
Agrawal MGhosh SSaxena NDiakonikolas IKempe DHenzinger M(2018)Bootstrapping variables in algebraic circuitsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188762(1166-1179)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188762
Minahan DVolkovich I(2017)Complete derandomization of identity testing and reconstruction of read-once formulasProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135627(1-13)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135627
Kumar MSaraf S(2016)Arithmetic circuits with locally low algebraic rankProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982479(1-27)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982479
Saxena NSeshadhri C(2013)From sylvester-gallai configurations to rank boundsJournal of the ACM10.1145/252840360:5(1-33)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2528403
Agrawal MSaha CSaptharishi RSaxena NKarloff HPitassi T(2012)Jacobian hits circuitsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214033(599-614)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214033

View Options

View options

Media

Figures

Other

Tables

View Table of Contents