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

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages867-875
Number of pages9
ISBN (Print)9781450327107
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States
Duration: May 31 2014Jun 3 2014

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other4th Annual ACM Symposium on Theory of Computing, STOC 2014
CountryUnited States
CityNew York, NY
Period5/31/146/3/14

Keywords

  • Derandomization
  • Polynomial identity testing
  • Read-once branching programs

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Hitting sets for multilinear read-once algebraic branching programs, in any order'. Together they form a unique fingerprint.

Cite this