Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-029 | 26th April 2018 17:13

Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs

RSS-Feed




Revision #1
Authors: Neeraj Kayal, Chandan Saha, vineet nair
Accepted on: 26th April 2018 17:13
Downloads: 82
Keywords: 


Abstract:

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to compute a given polynomial via an algebraic branching program. Here we devise an efficient algorithm for an average-case version of this problem. Specifically, given $w,d,n \in \mathbb{N}$ and blackbox access to the $w^2$ entries of a matrix product $F = X_1 \cdots X_d$ , where each $X_i$ is a $w \times w$ linear matrix over a given finite field $\mathbb{F}_q$, we wish to recover a factorization $F = Y_1 \cdots Y_{d'}$, where every $Y_i$ is also a linear matrix over $\mathbb{F}_q$ (or a small extension of $\mathbb{F}_q$). We show that when the input $F$ is sampled from a distribution defined by choosing random linear matrices $X_1, \ldots, X_d$ over $\mathbb{F}_q$ independently and taking their product and $n \geq 4w^2$ and the characteristic of $\mathbb{F}_q$ is at least $(ndw)^{\Omega(1)}$ then an equivalent factorization $F = Y_1 \cdots Y_d$ can be recovered in (randomized) time $(wdn \log q)^{O(1)}$. We also show that in this situation, if we are instead given a single entry of $F$ rather than its $w^2$ correlated entries then the recovery can be done in (randomized) time $(d^{w^3} n \log q)^{O(1)}$.



Changes to previous version:

The introduction has been altered to clarify the motivation and highlight the improvement over our previous work [Kayal, Nair, Saha, Tavenas {CCC 2017}].


Paper:

TR18-029 | 9th February 2018 09:24

Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs


Abstract:

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to compute a given polynomial via an algebraic branching program. Here we devise an efficient algorithm for an average-case version of this problem. Specifically, given $w,d,n \in \mathbb{N}$ and blackbox access to the $w^2$ entries of a matrix product $F = X_1 \cdots X_d$ , where each $X_i$ is a $w \times w$ linear matrix over a given finite field $\mathbb{F}_q$, we wish to recover a factorization $F = Y_1 \cdots Y_{d'}$, where every $Y_i$ is also a linear matrix over $\mathbb{F}_q$ (or a small extension of $\mathbb{F}_q$). We show that when the input $F$ is sampled from a distribution defined by choosing random linear matrices $X_1, \ldots, X_d$ over $\mathbb{F}_q$ independently and taking their product and $n \geq 4w^2$ and the characteristic of $\mathbb{F}_q$ is at least $(ndw)^{\Omega(1)}$ then an equivalent factorization $F = Y_1 \cdots Y_d$ can be recovered in (randomized) time $(wdn \log q)^{O(1)}$. We also show that in this situation, if we are instead given a single entry of $F$ rather than its $w^2$ correlated entries then the recovery can be done in (randomized) time $(d^{w^3} n \log q)^{O(1)}$.



ISSN 1433-8092 | Imprint