×

Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn’t matter. (English) Zbl 1272.68162

Summary: Let \(C\) be a depth-3 circuit with \(n\) variables, degree \(d\), and top-fanin \(k\) (called \({\Sigma\Pi\Sigma}(k,d,n)\) circuits) over base field \(\mathbb F\). It is a major open problem to design a deterministic polynomial-time blackbox algorithm that tests whether \(C\) is identically zero. A. R. Klivans and D. Spielman [“Randomness efficient identity testing of multivariate polynomials”, in: Proceedings of the 33rd annual symposium on theory of computing, STOC 2001. New York, NY: ACM Press. 216–223 (2001; doi:10.1145/380752.380801)] observed that the problem is open even when \(k\) is a constant. This case has been subjected to serious scrutiny over the past few years, starting from the work of Z. Dvir and A. Shpilka [SIAM J. Comput. 36, No. 5, 1404–1434 (2007; Zbl 1124.68042)]. We give the first polynomial-time blackbox algorithm for this problem. Our algorithm runs in time \(\text{poly}(n)d^k\), regardless of the base field. The only field for which polynomial-time algorithms were previously known is \(\mathbb F=\mathbb Q\) [N. Kayal and S. Saraf, “Blackbox polynomial identity testing for depth 3 circuits”, in: Proceedings of the 50th annual IEEE symposium on foundations of computer science, FOCS 2009. Los Alamitos: IEEE Computer Society. 198–207 (2009); 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 IEEE symposium on foundations of computer science, FOCS 2010. Los Alamitos: IEEE Computer Society. 21–29 (2010; doi:10.1109/FOCS.2010.9)]. This is the first blackbox algorithm for depth-3 circuits that does not use the rank-based approaches of Z. Karnin and A. Shpilka [“Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in”, in: Proceedings of the 24th annual IEEE conference on computational complexity, CCC 2009. Los Alamitos: IEEE Computer Society. 274–285 (2009; doi:10.1109/CCC.2009.18)]. 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 \({\Sigma\Pi\Sigma}(k,d,n)\) circuit to \(k\) variables but preserves the identity structure.

MSC:

68Q25 Analysis of algorithms and problem complexity
12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation

Citations:

Zbl 1124.68042