Abstract
In this paper we give the first deterministic polynomial time algorithm for testing whether a diagonal depth-3 circuit C(x 1,...,x n ) (i.e. C is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only if there are exponentially many linear functions. Our techniques generalize to the following new results:
-
1
Suppose we are given a depth-4 circuit (over any field \(\mathbb{F}\)) of the form:
$$C({x_1},\ldots,{x_n}):=\sum_{i=1}^k L_{i,1}^{e_{i,1}}\cdots L_{i,s}^{e_{i,s}}$$where, each L i,j is a sum of univariate polynomials in \(\mathbb{F}[{x_1},\ldots,{x_n}]\). We can test whether C is zero deterministically in poly(size(C), max i {(1 + e i,1) ⋯ (1 + e i,s)}) field operations. In particular, this gives a deterministic polynomial time identity test for general depth-3 circuits C when the d: =degree(C) is logarithmic in the size(C).
-
1
We prove that if the above circuit C(x 1,...,x n ) computes the determinant (or permanent) of an m×m formal matrix with a “small” \(s=o\left(\frac{m}{\log m}\right)\) then k = 2Ω(m). Our lower bounds work for all fields \(\mathbb{F}\). (Previous exponential lower bounds for depth-3 only work for nonzero characteristic.)
-
1
We also present an exponentially faster identity test for homogeneous diagonal circuits (deterministically in poly(nklog(d)) field operations over finite fields).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Adleman, L.M., Lenstra, H.W.: Finding irreducible polynomials over finite fields. In: 18th ACM Symposium on Theory of Computing, pp. 350–355. ACM Press, New York (1986)
Agrawal, M., Biswas, S.: Primality and identity testing via Chinese remaindering. Journal of the ACM 50(4), 429–443 (2003)
Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Annals of Mathematics 160(2), 781–793 (2004)
Agrawal, M., Vinay, V.: Arithmetic Circuits: A Chasm at Depth Four (preprint, 2008)
Arora, S., Safra, S.: Probabilistic Checking of Proofs: A New Characterization of NP. Journal of the ACM 45(1), 70–122 (1998)
Blum, M., Chandra, A.K., Wegman, M.N.: Equivalence of free Boolean graphs can be tested in polynomial time. Information Processing Letters 10, 80–82 (1980)
Clausen, M., Dress, A., Grabmeier, J., Karpinski, M.: On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science 84(2), 151–164 (1991)
Dvir, Z., Shpilka, A.: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput. 36(5), 1404–1434 (2007)
Grigoriev, D., Karpinski, M.: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. In: 30th ACM Symposium on Theory of Computing, pp. 577–582. ACM Press, New York (1998)
Grigoriev, D., Razborov, A.A.: Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Appl. Algebra Eng. Commun. Comput. 10(6), 465–487 (2000)
Impagliazzo, R., Kabanets, V.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1/2), 1–46 (2004)
Karnin, Z., Shpilka, A.: Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in. ECCC Report TR07-042 (2007)
Kayal, N.: Private Communication. Summer (2007)
Kayal, N., Saxena, N.: Polynomial Identity Testing for Depth 3 Circuits. Computational Complexity 16(2), 115–138 (2007)
Lovasz, L.: On determinants, matchings, and random algorithms. In: Fundamentals of Computing Theory, pp. 565–574. Akademia-Verlag (1979)
Nisan, N.: Lower bounds for non-commutative computation. In: 23rd ACM Symposium on Theory of Computing, pp. 410–418. ACM Press, New York (1991)
Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity 6(3), 217–234 (1997)
Raz, R.: Multi-linear formulas for permanent and determinant are of super-polynomial size. In: 36th ACM Symposium on Theory of Computing, pp. 633–641. ACM Press, New York (2004)
Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1), 1–19 (2005)
Schwartz, J.T.: Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM 27(4), 701–717 (1980)
Shamir, A.: IP=PSPACE. Journal of the ACM 39(4), 869–877 (1992)
Zippel, R.: Probabilistic Algorithms for Sparse Polynomials. In: International Symposium on Symbolic and Algebraic Computation, pp. 216–226. Springer, Heidelberg (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saxena, N. (2008). Diagonal Circuit Identity Testing and Lower Bounds. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol 5125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70575-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-70575-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70574-1
Online ISBN: 978-3-540-70575-8
eBook Packages: Computer ScienceComputer Science (R0)