License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.21
URN: urn:nbn:de:0030-drops-75318
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7531/
Kayal, Neeraj ;
Nair, Vineet ;
Saha, Chandan ;
Tavenas, Sébastien
Reconstruction of Full Rank Algebraic Branching Programs
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(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 b, where b 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 v = (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_{v,d}, the (1,1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to v in 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_{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:1--21:61},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-040-8},
ISSN = {1868-8969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7531},
URN = {urn:nbn:de:0030-drops-75318},
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 |
