Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-021 | 11th February 2017 13:35

Reconstruction of full rank Algebraic Branching Programs



An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms in $m$ variables over a field $\mathbb{F}$ (which we assume to be either $\mathbb{Q}$ or a field of characteristic $\text{poly}(m)$). The polynomial computed by A is the entry of the $1 \times 1$ matrix obtained from the product $\prod_{k=1}^{d} X_k$. 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,\dots ,X_d$ are $\mathbb{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 $\beta$, where $\beta$ is the bit length of the coefficients of $f$. The algorithm works even if $X_k$ is a $w_{k-1} \times w_k$ matrix (with $w_0 = w_d = 1$), and $\mathbf{w} = (w_1, \ldots, 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_{\mathbf{w},d}$, the $(1,1)$-th entry of a product of $d$ rectangular symbolic matrices whose dimensions are according to $\mathbf{w} \in \mathbb{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_{\mathbf{w},d}$ and the `layer spaces' of a full rank ABP computing $f$. This connection also helps determine the group of symmetries of $IMM_{\mathbf{w},d}$ and show that $IMM_{\mathbf{w},d}$ is characterized by its group of symmetries.

ISSN 1433-8092 | Imprint