Abstract
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 X_1 X_2 ... X_d. We say A is a full rank ABP if the w^2(d2) + 2w linear forms occurring in the matrices X_1, X_2, ... , X_d are Flinearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an mvariate 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 b, where b is the bit length of the coefficients of f. The algorithm works even if X_k is a w_{k1} x w_k matrix (with w_0 = w_d = 1), and v = (w_1, ..., w_{d1}) is unknown.
The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMM_{v,d}, the (1,1)th entry of a product of d rectangular symbolic matrices whose dimensions are according to v in N^{d1}. 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_{v,d} and the 'layer spaces' of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMM_{v,d} and show that IMM_{v,d} is characterized by its group of symmetries.
BibTeX  Entry
@InProceedings{kayal_et_al:LIPIcs:2017:7531,
author = {Neeraj Kayal and Vineet Nair and Chandan Saha and S{\'e}bastien Tavenas},
title = {{Reconstruction of Full Rank Algebraic Branching Programs}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {21:121:61},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7531},
URN = {urn:nbn:de:0030drops75318},
doi = {10.4230/LIPIcs.CCC.2017.21},
annote = {Keywords: Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra}
}
Keywords: 

Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra 
Collection: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

01.08.2017 