Reconstruction of Full Rank Algebraic Branching Programs
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas · ACM Transactions on Computation Theory · 2018
An algebraic branching program (ABP) A can be modelled as a product expression X 1 amp;middot; X 2 … X d , where X 1 and X d are 1 × w and w × 1 matrices, respectively, and every other X k 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 ∏ k=1 d X k . We say A is a full rank ABP if the w 2 ( d − 2) + 2 w 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 β, where β is the bit length of the coefficients of f . The algorithm works even if X k is a w k−1 × 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 IMM w, d , the (1, 1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to w ∈ N d −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 IMM w, d and the “layer spaces” of a full rank ABP computing f . This connection also helps determine the group of symmetries of IMM w, d and show that IMM w, d is characterized by its group of symmetries.