Name
Abstract | ||
|---|---|---|
We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in nO(log2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the model of read-once oblivious boolean branching programs with unknown order. We obtain our results by recasting, and improving upon, the ideas of Agrawal, Saha and Saxena [ASS13]. We phrase the ideas in terms of rank condensers and Wronskians, and show that our results improve upon the classical multivariate Wronskian, which may be of independent interest. In addition, we give the first nO(lg lg n) black-box polynomial identity testing algorithm for the so called model of diagonal circuits. This result improves upon the nΘ(lg n)-time algorithms given by Agrawal, Saha and Saxena [ASS13], and Forbes and Shpilka [FS13b] for this class. More generally, our result holds for any model computing polynomials whose partial derivatives (of all orders) span a low dimensional linear space. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2591796.2591816 | STOC |
Keywords | Field | DocType |
algorithms,polynomial identity testing,read-once branching programs,theory,de-randomization,numerical algorithms and problems | Diagonal,Polynomial identity testing,Discrete mathematics,Combinatorics,Algebraic number,Polynomial,Wronskian,Linear space,Partial derivative,Multilinear map,Mathematics | Conference |
Citations | PageRank | References |
20 | 0.71 | 50 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Forbes | 1 | 97 | 8.99 |
| Ramprasad Saptharishi | 2 | 184 | 13.72 |
| Amir Shpilka | 3 | 1095 | 64.27 |