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 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 d k =1 X k . We say A is a ful l ran k 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 IM M 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 IM M w d and the `layer spaces' of a full rank ABP computing f . This connection also helps determine the group of symmetries of IM M w d and show that IM M w d is characterized by its group of symmetries.