Average-case linear matrix factorization and reconstruction of low width algebraic branching programs

摘要: A matrix X is called a linear if its entries are affine forms, i.e., degree one polynomials in n variables. What minimal-sized representation of given F as product matrices? Finding such minimal closely related to finding an optimal way compute polynomial via algebraic branching program. Here we devise efficient algorithm for average-case version this problem. Specifically, $$w,d,n \in \mathbb{N}$$ and blackbox access the w2 $$F = X_1 \cdots X_d$$ , where each $$X_i$$ $$w \times w$$ over finite field $$\mathbb{F}_q$$ wish to recover factorization Y_1 Y_{d'}$$ every $$Y_i$$ is also (or small extension of ). We show that when input sampled from a distribution defined by choosing random matrices $$X_1, \ldots, independently taking their and $$n \geq 4w^2$$ $${\rm char}(\mathbb{F}_q) (dn)^{\varOmega(1)}$$ then an equivalent Y_d$$ can be recovered in (randomized) time $$(dn \log q)^{O(1)}$$ . In fact, give a (worst-case) randomized factor any non-degenerate or pure (a notion define in the paper) into matrices; \cdots X_d$$ with high probability 's chosen independently at random. situation, we are instead single entry rather than w2 correlated entries, recovery done (randomized) time $$(d^{w^3}