Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
Authors:
- Manindra AgrawalMAManindra Agrawal
- Rohit GurjarRGRohit Gurjar
- Arpita KorwarAKArpita Korwar
- Nitin SaxenaNSNitin Saxena
- 1 January 2015
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 44 (3) , 669-697
Abstract
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 Forbes, Saptharishi, and Shpilka [Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875]. 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 Forbes and Shpilka [Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 243--252]) and also with the depth-3 set-multilinear circuits (due to Agrawal, Saha, and Saxena [Proceedings of the 2013 ACM Symposium on Theory of Computing, 2013, pp. 321--330]). 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 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 [M. A. Forbes, R. Saptharishi, and A. Shpilka, Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875].
Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- The GCT program toward the P vs. NP problemCommunications of the ACM, 2012
- An Almost Optimal Rank Bound for Depth-3 IdentitiesSIAM Journal on Computing, 2011
- Arithmetic Circuits: A Survey of Recent Results and Open QuestionsFoundations and Trends® in Theoretical Computer Science, 2010
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 CircuitsSIAM Journal on Computing, 2007
- Primality and identity testing via Chinese remainderingJournal of the ACM, 2003
- Pseudorandom generators for space-bounded computationCombinatorica, 1992
- Computing Algebraic Formulas Using a Constant Number of RegistersSIAM Journal on Computing, 1992
- On computing the determinant in small parallel time using a small number of processorsInformation Processing Letters, 1984
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978