TY - GEN

T1 - Hitting sets for multilinear read-once algebraic branching programs, in any order

AU - Forbes, Michael A.

AU - Saptharishi, Ramprasad

AU - Shpilka, Amir

PY - 2014

Y1 - 2014

N2 - We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in nO(lg2 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.

AB - We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in nO(lg2 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.

KW - Derandomization

KW - Polynomial identity testing

KW - Read-once branching programs

UR - http://www.scopus.com/inward/record.url?scp=84904344973&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904344973&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591816

DO - 10.1145/2591796.2591816

M3 - Conference contribution

AN - SCOPUS:84904344973

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 867

EP - 875

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -