 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: https://drops.dagstuhl.de/opus/volltexte/2017/7531/
 Go to the corresponding LIPIcs Volume Portal

### Reconstruction of Full Rank Algebraic Branching Programs

 pdf-format:

### 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},
DROPS-Home | Fulltext Search | Imprint | Privacy 