English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give deterministic black-box polynomial identity testing algorithms formultilinear read-once oblivious algebraic branching programs (ROABPs), inn^(lg^2 n) time. Further, our algorithm is oblivious to the order of thevariables. This is the first sub-exponential time algorithm for this model.Furthermore, our result has no known analogue in the model of read-onceoblivious boolean branching programs with unknown order, as despite recent workthere is no known pseudorandom generator for this model with sub-polynomialseed-length (for unbounded-width branching programs).  This result extends and generalizes the result of Forbes and Shpilka thatobtained a n^(lg n)-time algorithm when given the order. We also extend andstrengthen the work of Agrawal, Saha and Saxena that gave a black-box algorithmrunning in time exp((lg n)^d) for set-multilinear formulas of depth d. We notethat the model of multilinear ROABPs contains the model of set-multilinearalgebraic branching programs, which itself contains the model ofset-multilinear formulas of arbitrary depth. We obtain our results byrecasting, and improving upon, the ideas of Agrawal, Saha and Saxena. We phrasethe ideas in terms of rank condensers and Wronskians, and show that our resultsimprove upon the classical multivariate Wronskian, which may be of independentinterest.  In addition, we give the first n^(lglg n) black-box polynomial identitytesting algorithm for the so called model of diagonal circuits. This model,introduced by Saxena has recently found applications in the work of Mulmuley,as well as in the work of Gupta, Kamath, Kayal, Saptharishi. Previously workhad given n^(lg n)-time algorithms for this class. More generally, our resultholds for any model computing polynomials whose partial derivatives (of allorders) span a low dimensional linear space.

Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order