×

Hitting-sets for ROABP and sum of set-multilinear circuits. (English) Zbl 1327.68339

Summary: We give an \(n^{O(\log n)}\)-time (\(n\) is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious arithmetic branching programs (ROABPs). The best time complexity known for blackbox polynomial identity testing (PIT) for this class was \(n^{O(\log^2 n)}\) due to M. A. Forbes et al. [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14. New York, NY: Association for Computing Machinery (ACM). 867–875 (2014; Zbl 1315.68127)]. Moreover, their result holds only when the individual degree is small, while we do not need any such assumption. With this, we match the time complexity for the unknown-order ROABP with the known-order ROABP (due to M. A. Forbes and A. Shpilka [“Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs”, in: Proceedings of the IEEE 54th annual symposium on foundations of computer science, FOCS’13. Los Alamitos, CA: IEEE Computer Society. 243–252 (2013; doi:10.1109/FOCS.2013.34)]) and also with the depth-3 set-multilinear circuits (due to M. Agrawal et al. [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. New York, NY: Association for Computing Machinery (ACM). 321–330 (2013; Zbl 1293.94140)]). Our proof is simpler and involves a new technique called basis isolation. The depth-3 model has recently gained much importance, as it has become a stepping stone to understanding general arithmetic circuits. Multilinear depth-3 circuits are known to have exponential lower bounds but no polynomial time blackbox identity tests. In this paper, we take a step toward designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-3 circuits. To achieve this, we define the notions of distance and base sets. Distance, for a multilinear depth-3 circuit (say, in \(n\) variables and \(k\) product gates), measures how far the variable partitions corresponding to the product gates are from being a mere refinement of each other. The 1-distance circuits strictly contain the set-multilinear model, while \(n\)-distance captures general multilinear depth-3. We design a hitting-set in time \((nk)^{O(\Delta \log n)}\) for \(\Delta\)-distance. Further, we give an extension of our result to models where the distance is large (close to \(n\)) but is small when restricted to certain base sets (of variables). We also explore a new model of ROABPs where the factor matrices are invertible (called invertible-factor ROABPs). We design a hitting-set in time \(\mathrm{poly}(n^{w^2})\) for width-\(w\) invertible-factor ROABPs. Further, we could do without the invertibility restriction when \(w=2\). Previously, the best result for width-2 ROABPs was quasi-polynomial time [Forbes et al., loc. cit.].

MSC:

68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

References:

[1] M. Agrawal, {\it Proving lower bounds via pseudo-random generators}, in FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Comput. Sci. 3821, Springer, Berlin, 2005, pp. 92-105. · Zbl 1172.68479
[2] M. Agrawal and S. Biswas, {\it Primality and identity testing via Chinese remaindering}, J. ACM, 50 (2003), pp. 429-443. · Zbl 1325.68253
[3] M. Agrawal, R. Gurjar, A. Korwar, and N. Saxena, {\it Hitting-sets for low-distance multilinear depth-3}, Electronic Colloquium on Computational Complexity (ECCC), 20 (2013), 174.
[4] M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena, {\it Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-\(3\) transcendence degree-k circuits}, in Proceedings of the 2012 ACM Symposium on Theory of Computing (STOC), 2012, pp. 599-613. · Zbl 1286.94115
[5] M. Agrawal, C. Saha, and N. Saxena, {\it Quasi-polynomial hitting-set for set-depth-\(Δ\) formulas}, in Proceedings of the 2013 ACM Symposium on Theory of Computing (STOC), 2013, pp. 321-330. · Zbl 1293.94140
[6] E. Allender and F. Wang, {\it On the power of algebraic branching programs of width two}, in Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci. 6755, Springer, Heidelberg, 2011, pp. 736-747. · Zbl 1333.68131
[7] M. Ben-Or and R. Cleve, {\it Computing algebraic formulas using a constant number of registers}, SIAM J. Comput., 21 (1992), pp. 54-58. · Zbl 0743.68062
[8] S. J. Berkowitz, {\it On computing the determinant in small parallel time using a small number of processors}, Inform. Process. Lett., 18 (1984), pp. 147-150. · Zbl 0541.68019
[9] A. Bogdanov, Z. Dvir, E. Verbin, and A. Yehudayoff, {\it Pseudorandomness for width-\(2\) branching programs}, Theory Comput., 9 (2013), pp. 283-292. · Zbl 1300.68037
[10] A. De, {\it Pseudorandomness for permutation and regular branching programs}, in Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011, pp. 221-231.
[11] R. M. de Oliveira, A. Shpilka, and B. L. Volk, {\it Subexponential size hitting sets for bounded depth multilinear formulas}, Electronic Colloquium on Computational Complexity (ECCC), 21 (2014), 157 (to appear in Proceedings of the 2015 IEEE Conference on Computational Complexity). · Zbl 1388.68132
[12] R. A. Demillo and R. J. Lipton, {\it A probabilistic remark on algebraic program testing}, Inform. Process. Lett., 7 (1978), pp. 193-195. · Zbl 0397.68011
[13] Z. Dvir and A. Shpilka, {\it Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits}, SIAM J. Comput., 36 (2007), pp. 1404-1434. · Zbl 1124.68042
[14] M. A. Forbes, R. Saptharishi, and A. Shpilka, {\it Hitting sets for multilinear read-once algebraic branching programs, in any order}, in Proceedings of the 2014 ACM Symposium on Theory of Computing (STOC), 2014, pp. 867-875. · Zbl 1315.68127
[15] M. A. Forbes and A. Shpilka, {\it On identity testing of tensors, low-rank recovery and compressed sensing}, in Proceedings of the 2012 ACM Symposium on Theory of Computing (STOC), 2012, pp. 163-171. · Zbl 1286.68489
[16] M. A. Forbes and A. Shpilka, {\it Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs}, in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013, pp. 243-252.
[17] A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi, {\it Arithmetic circuits: A chasm at depth three}, in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013, pp. 578-587. · Zbl 1344.68300
[18] R. Gurjar, A. Korwar, N. Saxena, and T. Thierauf, {\it Deterministic identity testing for sum of read once ABPs}, Electronic Colloquium on Computational Complexity (ECCC), 21 (2014), 158 (to appear in Proceedings of the 2015 IEEE Conference on Computational Complexity). · Zbl 1388.68118
[19] R. Impagliazzo, R. Meka, and D. Zuckerman, {\it Pseudorandomness from shrinkage}, in Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), 2012, pp. 111-119. · Zbl 1427.68096
[20] M. J. Jansen, Y. Qiao, and J. Sarma, {\it Deterministic black-box identity testing \(π\)-ordered algebraic branching programs}, in Proceedings of the 30th International Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs. Leibniz. Int. Proc. Inform. 8, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2010, pp. 296-307. · Zbl 1245.68109
[21] M. J. Jansen, Y. Qiao, and J. Sarma, {\it Deterministic identity testing of read-once algebraic branching programs}, Electronic Colloquium on Computational Complexity (ECCC), 17 (2010), 84. · Zbl 1245.68109
[22] Z. S. Karnin and A. Shpilka, {\it Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in}, Combinatorica, 31 (2011), pp. 333-364. · Zbl 1274.68133
[23] N. Kayal and S. Saraf, {\it Blackbox polynomial identity testing for depth 3 circuits}, in Proceedings of the 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 198-207. · Zbl 1292.68095
[24] N. Kayal and N. Saxena, {\it Polynomial identity testing for depth \(3\) circuits}, Comput. Complexity, 16 (2007), pp. 115-138. · Zbl 1173.94470
[25] A. R. Klivans and D. A. Spielman, {\it Randomness efficient identity testing of multivariate polynomials}, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001, pp. 216-223. · Zbl 1323.68563
[26] M. Koucký, P. Nimbhorkar, and P. Pudlák, {\it Pseudorandom generators for group products}, extended abstract, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, pp. 263-272. · Zbl 1288.68131
[27] L. Kronecker, {\it Grundzüge einer arithmetischen Theorie der algebraischen Grössen}, G. Reimer, Berlin, 1882. · JFM 14.0038.02
[28] M. Mahajan and V. Vinay, {\it Determinant: Combinatorics, algorithms, and complexity}, Chicago J. Theoret. Comput. Sci., 1997 (1997), 5. · Zbl 0924.68088
[29] K. D. Mulmuley, {\it The GCT program toward the P vs. NP problem}, Commun. ACM, 55 (2012), pp. 98-107.
[30] K. D. Mulmuley, {\it Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma}, in Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), 2012, pp. 629-638.
[31] N. Nisan, {\it Pseudorandom generators for space-bounded computation}, Combinatorica, 12 (1992), pp. 449-461. · Zbl 0759.68024
[32] N. Nisan, {\it Lower bounds for non-commutative computation}, extended abstract, in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 410-418.
[33] R. Raz and A. Shpilka, {\it Deterministic polynomial identity testing in non-commutative models}, Comput. Complexity, 14 (2005), pp. 1-19. · Zbl 1096.68070
[34] R. Raz and A. Yehudayoff, {\it Lower bounds and separations for constant depth multilinear circuits}, Comput. Complexity, 18 (2009), pp. 171-207. · Zbl 1213.68319
[35] O. Reingold, T. Steinke, and S. P. Vadhan, {\it Pseudorandomness for regular branching programs via Fourier analysis}, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013, Springer, Berlin, Heidelberg, pp. 655-670. · Zbl 1359.68054
[36] C. Saha, R. Saptharishi, and N. Saxena, {\it The power of depth 2 circuits over algebras}, in Foundations of Software Technology and Theoretical Computer Science–FSTTCS 2009, LIPIcs. Leibniz. Int. Proc. Inform. 4, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2009, pp. 371-382. · Zbl 1248.68262
[37] C. Saha, R. Saptharishi, and N. Saxena, {\it A case of depth-3 identity testing, sparse factorization and duality}, Comput. Complexity, 22 (2013), pp. 39-69. · Zbl 1311.68201
[38] N. Saxena, {\it Diagonal circuit identity testing and lower bounds}, in Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci. 5125, Springer, Berlin, 2008, pp. 60-71. · Zbl 1152.68703
[39] N. Saxena, {\it Progress on polynomial identity testing}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, no. 99 (2009), pp. 49-79. · Zbl 1188.68154
[40] N. Saxena, {\it Progress on polynomial identity testing-II}, in Perspectives in Computational Complexity, Progr. Comput. Sci. Appl. Logic 26, M. Agrawal and V. Arvind, eds., Springer International Publishing, Cham, Switzerland, 2014, pp. 131-146. · Zbl 1345.68182
[41] N. Saxena and C. Seshadhri, {\it An almost optimal rank bound for depth-\(3\) identities}, SIAM J. Comput., 40 (2011), pp. 200-224. · Zbl 1216.68133
[42] N. Saxena and C. Seshadhri, {\it Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn’t matter}, SIAM J. Comput., 41 (2012), pp. 1285-1298. · Zbl 1272.68162
[43] N. Saxena and C. Seshadhri, {\it From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-\(3\) circuits}, J. ACM, 60 (2013), 33. · Zbl 1281.68231
[44] J. T. Schwartz, {\it Fast probabilistic algorithms for verification of polynomial identities}, J. ACM, 27 (1980), pp. 701-717. · Zbl 0452.68050
[45] A. Shpilka and A. Yehudayoff, {\it Arithmetic circuits: A survey of recent results and open questions}, Found. Trends Theor. Comput. Sci., 5 (2009), pp. 207-388. · Zbl 1205.68175
[46] T. Steinke, {\it Pseudorandomness for permutation branching programs without the group theory}, Electronic Colloquium on Computational Complexity (ECCC), 19 (2012), 83.
[47] T. Steinke, S. Vadhan, and A. Wan, {\it Pseudorandomness and Fourier growth bounds for width 3 branching programs}, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl, Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken, Wadern, Germany, 2014, pp. 885-899. · Zbl 1359.68055
[48] S. Toda, {\it Counting Problems Computationally Equivalent to Computing the Determinant}, Technical Report CSIM 91-07, Department of Computer Science and Information Mathematics, University of Electro-Communications, Tokyo, 1991.
[49] R. Zippel, {\it Probabilistic algorithms for sparse polynomials}, in Proceedings of the International Symposium on Symbolic and Algebraic Computation (EUROSAM ’79), Springer-Verlag, London, 1979, pp. 216-226. · Zbl 0418.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.