Name
Abstract | ||
|---|---|---|
An algebraic branching program (ABP) A can be modelled as a product expression X1amp;middot; X2… Xd, where X1 and Xd are 1 × w and w × 1 matrices, respectively, and every other Xk 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 ∏k=1d Xk. We say A is a full rank ABP if the w2(d − 2) + 2w linear forms occurring in the matrices X1, X2, …, Xd 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 Xk is a wk−1 × wk matrix (with w0 = wd = 1), and w = (w1, …, wd − 1) is unknown. The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMMw, d, the (1, 1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to w ∈ Nd−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 IMMw, d and the “layer spaces” of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMMw, d and show that IMMw, d is characterized by its group of symmetries.
|
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.CCC.2017.21 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | DocType | Volume |
Iterated matrix multiplication, Lie algebra, equivalence testing, group of symmetries, layer spaces | Conference | 24 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Vineet Nair | 2 | 0 | 0.34 |
| Chandan Saha | 3 | 227 | 16.91 |
| Sébastien Tavenas | 4 | 14 | 5.19 |