Reconstruction of Full Rank Algebraic Branching Programs

An algebraic branching program (ABP) A can be modelled as a product expression X-1.X-2...X-d,where X-1 and X-d are 1 x w and w x 1 matrices, respectively, and every other X-k is a w x 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 x 1 matrix obtained from the product Pi(d)(k=1) X-k. We say A is a full rank ABP if the w(2)(d - 2) + 2w linear forms occurring in the matrices X-1, X-2, ..., X-d 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 beta, where beta is the bit length of the coefficients of f. The algorithm works even if X-k is a w(k-1) x w(k) matrix (with w(0) = w(d) = 1), and w = (w(1), ..., w(d - 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 is an element of 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.