Abstract
In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form \(f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} \), where each h i is a polynomial that depends on only ρ linear functions, and each g i is a product of linear functions (when h i = 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When max i (deg(h i · g i )) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.
-
1.
A deterministic black-box identity testing algorithm for ΣΠΣ(k; d;ρ) circuits that runs in quasi-polynomial time (for ρ=polylog(n+d)). In particular this gives the first black-box quasi-polynomial time PIT algorithm for depth-3 circuits with k multiplication gates.
-
2.
A deterministic black-box identity testing algorithm for read-k ΣΠΣ circuits (depth-3 circuits where each variable appears at most k times) that runs in time \(n^{2^{O(k^2 )} } \). In particular this gives a polynomial time algorithm for k=O(1).
Our results give the first sub-exponential black-box PIT algorithm for circuits of depth higher than 2. Another way of stating our results is in terms of test sets for the underlying circuit model. A test set is a set of points such that if two circuits get the same values on every point of the set then they compute the same polynomial. Thus, our first result gives an explicit test set, of quasi-polynomial size, for ΣΠΣ(k; d;ρ) circuits (when ρ=polylog(n+d)). Our second result gives an explicit polynomial size test set for read-k depth-3 circuits.
The proof technique involves a construction of a family of affine subspaces that have a rank-preserving property that is inspired by the construction of linear seeded extractors for affine sources of Gabizon and Raz [9], and a generalization of a theorem of [8] regarding the structure of identically zero depth-3 circuits with bounded top fan-in.
Similar content being viewed by others
References
M. Agrawal and S. Biswas: Primality and identity testing via chinese remaindering, JACM, 50(4) (2003), 429–443.
M. Agrawal: Proving lower bounds via pseudo-random generators, In Proceedings of the 25th FSTTCS, volume 3821 of LNCS, pages 92–105, 2005.
V. Arvind and P. Mukhopadhyay: The monomial ideal membership problem and polynomial identity testing, In Proceedings of the 18th ISAAC, pages 800–811, 2007.
M. Ben-or and P. Tiwari: A deterministic algorithm for sparse multivariate poly-nominal interpolation, In Proceedings of the 20th Annual STOC, pages 301–309, 1988.
S. Chari, P. Rohatgi, and A. Srinivasan: Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM J. on Computing, 24(5) (1995), 1036–1050.
Z. Chen and M. Kao: Reducing randomness via irrational numbers, SIAM J. on Computing, 29(4) (2000), 1247–1256.
M. Clausen, A. W. M. Dress, J. Grabmeier, and M. Karpinski: On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields, Theoretical Computer Science, 84(2) (1991), 151–164.
Z. Dvir and A. Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, SIAM J. on Computing, 36(5) (2006), 1404–1434.
A. Gabizon and R. Raz: Deterministic extractors for affine sources over large fields. In 46th Annual FOCS, pages 407–418, 2005.
D. Grigoriev and M. Karpinski: The matching problem for bipartite graphs with polynomially bounded permanents is in NC (extended abstract), In Proceedings of the 28th Annual FOCS, pages 166–172, 1987.
D. Grigoriev, M. Karpinski, and M. F. Singer: Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM J. on Computing, 19(6) (1990), 1059–1063.
V. Kabanets and R. Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, 13(1–2) (2004), 1–46.
Z. S. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich: Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. To appear in STOC, 2010.
M. Karpinski and I. Shparlinski: On some approximation problems concerning sparse polynomials over finite fields, Theoretical Computer Science, 157(2) (1996), 259–266.
N. Kayal and S. Saraf: Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual FOCS, pages 198–207, 2009.
N. Kayal and N. Saxena: Polynomial identity testing for depth 3 circuits. In Proceedingds of the 21st Annual IEEE Conference on Computational Complexity, pages 9–17, 2006.
A. Klivans and D. Spielman: Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual STOC, pages 216–223, 2001.
D. Lewin and S. Vadhan: Checking polynomial identities over any field: Towards a derandomization? In Proceedings of the 30th Annual STOC, pages 428–437, 1998.
L. Lovsz: On determinants, matchings, and random algorithms. In L. Budach, editor, Fundamentals of Computing Theory, Akademia-Verlag, 1979.
K. Mulmuley, U. Vazirani, and V. Vazirani: Matching is as easy as matrix inversion. Combinatorica, 7(1) (1987), 105–113.
R. Raz and A. Shpilka: Deterministic polynomial identity testing in non commutative models. Computational Complexity, 14(1) (2005), 1–19.
N. Saxena and C. Seshadhri: An almost optimal rank bound for depth-3 identities. In Proceedings of the 24th annual CCC, pages 137–148, 2009.
R. E. Schapire and L. M. Sellie: Learning sparse multivariate polynomials over a field with queries and counterexamples. J. of Computer and System Sciences, 52(2) (1996), 201–213.
J. T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. JACM, 27(4) (1980), 701–717.
A. Shpilka: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. on Computing, 38(6) (2009), 2130–2161.
A. Shpilka and I. Volkovich: Read-once polynomial identity testing. In Proceedings of the 40th Annual STOC, pages 507–516, 2008.
A. Shpilka and I. Volkovich: Improved polynomial identity testing for read-once formulas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop RANDOM, LNCS, pages 700–713, 2009.
K. Werther: The complexity of sparse polynomial interpolation over finite fields. Applicable Algebra in Engineering, Communication and Computing, 5 (1994), 91–103.
R. Zippel: Probabilistic algorithms for sparse polynomials. In Symbolic and algebraic computation, pages 216–226. 1979.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by the Israel Science Foundation (grant number 439/06).
Rights and permissions
About this article
Cite this article
Karnin, Z.S., Shpilka, A. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica 31, 333–364 (2011). https://doi.org/10.1007/s00493-011-2537-3
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-011-2537-3