Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

ABSTRACT

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called ΣΠΣ(k,d,n) circuits) over base field FF. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests if C is identically zero. Klivans & Spielman (STOC 2001) observed that the problem is open even when k is a constant. This case has been subjected to a serious study over the past few years, starting from the work of Dvir & Shpilka (STOC 2005).

We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time poly(n)d^k, regardless of the base field. The only field for which polynomial time algorithms were previously known is FF = QQ (Kayal & Saraf, FOCS 2009, and Saxena & Seshadhri, FOCS 2010). This is the first blackbox algorithm for depth-$3$ circuits that does not use the rank based approaches of Karnin & Shpilka (CCC 2008).

We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a ΣΠΣ(k,d,n) circuit to k variables, but preserves the identity structure.

References

1. M. Agrawal and S. Biswas. Primality and identity testing via Chinese remaindering. Journal of the ACM, 50(4):429--443, 2003. (Conference version in FOCS 1999).
2. M. Agrawal. Proving lower bounds via pseudo-random generators. In Proceedings of the 25th Annual Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 92--105, 2005.
3. M. Agrawal. Determinant versus permanent. In Proceedings of the 25th International Congress of Mathematicians (ICM), volume 3, pages 985--997, 2006.
4. L. M. Adleman and H. W. Lenstra. Finding irreducible polynomials over finite fields. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pages 350--355, 1986.
5. V. Arvind and P. Mukhopadhyay. The monomial ideal membership problem and polynomial identity testing. In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), pages 800--811, 2007.
6. M. Agrawal and R. Saptharishi. Classifying polynomials and identity testing. In Current Trends in Science, Indian Academy of Sciences, pages 149--162. 2009.
7. M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual Symposium on Foundations of Computer Science (FOCS), pages 67--75, 2008.
8. M. Anderson, D. van Melkebeek, and I. Volkovich. Derandomizing polynomial identity testing for multilinear constant-read formulae. In Proceedings of the 26th Conference on Computational Complexity (CCC), 2011.
9. M. Beecken, J. Mittmann, and N. Saxena. Algebraic independence and blackbox identity testing. Technical Report TR11-022, ECCC, 2011.
10. M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation. In Proceedings of the 20th annual ACM symposium on Theory of computing (STOC), pages 301--309, 1988.
11. 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):151--164, 1991.
12. Z. Chen and M. Kao. Reducing randomness via irrational numbers. In Proceedings of the 29th annual ACM symposium on Theory of computing (STOC), pages 200--209, 1997.
13. 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):1404--1434, 2006. (Conference version in STOC 2005).
14. D. Grigoriev, M. Karpinski, and M. F. Singer. Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comput., 19(6):1059--1063, 1990.
15. A. Gabizon and R. Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415--440, 2008. (Conference version in FOCS 2005).
16. J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the twelfth annual ACM Symposium on Theory of Computing, pages 262--272, 1980.
17. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1):1--46, 2004. (Conference version in STOC 2003).
18. Z. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich. Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 649--658, 2010.
19. M. Karpinski and I. Shparlinski. On some approximation problems concerning sparse polynomials over finite fields. Theoretical Computer Science, 157(2):259--266, 1996.
20. A. Klivans and D. A. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Symposium on Theory of Computing (STOC), pages 216--223, 2001.
21. N. Kayal and N. Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115--138, 2007. (Conference version in CCC 2006).
22. Z. Karnin and A. Shpilka. 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), pages 280--291, 2008.
23. Z. S. Karnin and A. Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24th Annual Conference on Computational Complexity (CCC), pages 274--285, 2009.
24. N. Kayal and S. Saraf. Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pages 198--207, 2009.
25. D. Lewin and S. Vadhan. Checking polynomial identities over any field: Towards a derandomization? In Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC), pages 428--437, 1998.
26. R. Raz. Tensor-rank and lower bounds for arithmetic formulas. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010.
27. R. Raz and A. Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1--19, 2005. (Conference version in CCC 2004).
28. N. Saxena. Diagonal circuit identity testing and lower bounds. In Proceedings of the 35th Annual International Colloquium on Automata, Languages and Programming (ICALP), pages 60--71, 2008.
29. N. Saxena. Progress on polynomial identity testing. Bulletin of the European Association for Theoretical Computer Science (EATCS)- Computational Complexity Column, (99):49--79, 2009.
30. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701--717, 1980.
31. R. E. Schapire and L. M. Sellie. Learning sparse multivariate polynomials over a field with queries and counterexamples. Journal of Computer and System Sciences, 52(2):201--213, 1996.
32. N. Saxena and C. Seshadhri. 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), pages 21--29, 2010.
33. N. Saxena and C. Seshadhri. From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits. Technical Report TR10-013 (Revision #1), ECCC, http://eccc.hpi-web.de/report/2010/013/, 2010.
34. N. Saxena and C. Seshadhri. An Almost Optimal Rank Bound for Depth-$3$ Identities. SIAM J. Comp., 40(1):200--224, 2011. (Conference version in CCC 2009).
35. C. Saha, R. Saptharishi, and N. Saxena. A case of depth-3 identity testing, sparse factorization and duality. Technical Report TR11-021, ECCC, 2011.
36. A. Shpilka and I. Volkovich. Improved polynomial identity testing for read-once formulas. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), pages 700--713, 2009.
37. S. Saraf and I. Volkovich. Black-box identity testing of depth-4 multilinear circuits. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), 2011.
38. A. Shpilka and A. Yehudayoff. Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3--4):207--388, 2010.
39. K. Werther. The complexity of sparse polynomial interpolation over finite fields. Applicable Algebra in Engineering, Communication and Computing, 5:91--103, 1994.
40. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Manipulation (EUROSAM), pages 216--226, 1979.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures