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

An algebraic branching program (ABP) A can be modelled as a product expression X1 ·X2 . . . Xd, where X1 and Xd are 1×w and w×1 matrices respectively, and every other Xk is a w×w matrix; the entries of these matrices are linear forms in m variables over a field F (which we assume to be either Q or a field of characteristic poly(m)). The polynomial computed by A is the entry of the 1 × 1 matrix obtained from the product ∏d k=1 Xk. We say A is a full rank ABP if the w2(d− 2) + 2w linear forms occurring in the matrices X1, X2, . . . , Xd are F-linearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an m-variate polynomial f of degree at most m, the algorithm outputs a full rank ABP computing f if such an ABP exists, or outputs ‘no full rank ABP exists’ (with high probability). The running time of the algorithm is polynomial in m and β, where β is the bit length of the coefficients of f . The algorithm works even if Xk is a wk−1 × wk matrix (with w0 = wd = 1), and w = (w1, . . . , wd−1) is unknown. The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMMw,d, the (1, 1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to w ∈ Nd−1. At its core, the algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMMw,d and the ‘layer spaces’ of a full rank ABP computing f . This connection also helps determine the group of symmetries of IMMw,d and show that IMMw,d is characterized by its group of symmetries. 1998 ACM Subject Classification F.1.3 Complexity Measures and Classes

Reconstruction of Full Rank Algebraic Branching Programs