Tag - Complexity theory

A matrix X is called a linear matrix if all its entries are affine forms. Given oracle access to w² degree d polynomials in n variables that are entries of a w × w matrix F, we wish to compute a factorization of F as a product of linear matrices, if such a factorization exists. Finding such a representation is closely related to finding an optimal way to compute a given polynomial via an algebraic branching program. Over rationals and finite fields of sufficiently large characteristic, we give a poly(n,d,b) time randomized algorithm to compute such a factorization in the average-case, when w ≤ √n/2. Here b is the bit length of the coefficients of the polynomials in F. Over finite fields the output of our algorithm is over the base field, whereas over ℚ the output is over a small extension of ℚ. Our algorithm actually gives an efficient worst-case randomized reconstruction algorithm for pure matrix products (which is a non-degeneracy notion that we define in this work). Additionally, we show that if we are given just one entry of F then we can recover a suitable factorization in poly(d^w3,n,b) time.

We will begin with a brief survey of known results on learning arithmetic circuits and its connection to lower bounds. Then we will discuss two results in details: sparse polynomial interpolation and reconstruction of read-once oblivious algebraic branching programs (ROABP). If time permits, we will give an overview of Kaltofen's polynomial factorization. The first tutorial will end with a short discussion on how the ROABP reconstruction technique (as it is) does not work for some other models for which good lower bounds are known, and the "need" for considering non-degenerate circuits. The second tutorial will focus on a recently introduced paradigm for learning non-degenerate circuits. The paradigm is based on decomposing a vector space into subspaces that remain invariant under the action of suitable linear operator spaces. We plan to demonstrate the effectiveness of this paradigm by considering non-degenerate homogeneous depth three circuits, depth four powering circuits etc.

Let C be an arithmetic circuit given as input that computes a polynomial f ∈ 𝔽[X], X = {x₁,x₂,…,x_n}. We obtain new algorithms for the following two problems first studied by Koutis and Williams. (k,n)-MLC: Compute the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. k-MMD: Test if there is a non-zero degree-k multilinear monomial in the polynomial f.

* Our algorithms are based on the fact that the Hadamard product f∘S_n,k, is the degree-k multilinear part of f, where S_n,k is the kth elementary symmetric polynomial.

* Our approach to computing f∘S_n,k involves a symmetrization trick which leads us to study the non-commutative symmetrized elementary symmetric polynomial S_n,k^∗ defined by Nisan. We obtain an explicit O^∗((n choose ↓k/2)) size algebraic branching program (ABP) for S_n,k^∗, and an explicit O∗(2^k) size ABP for a polynomial weakly equivalent to S_n,k^∗. We also briefly discuss the complexity of other polynomials related to S_n,k^∗: rectangular permanent and rectangular determinant.

* As applications of our explicit ABP construction of S_n,k^∗ mentioned above, for (k,n)-MLC we get a deterministic algorithm of run time O∗(n^k/2+clogk) (where c is a constant), answering an open question in Koutis and Williams. As corollaries we get O∗((n choose ↓k/2))-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating set, m-Dimensional k-Matching.

* For k-MMD we obtain a randomized algorithm of 4.32^k⋅poly(n,s) time and poly(n,k,s) space. This matches the run time of a recent algorithm for k-MMD which requires exponential (in k) space.

We will discuss a short and self contained proof (based on joint work with Chi-Ning Chou and Noam Solomon) of a classical result of Kaltofen from the mid 1980s where he showed that if an n-variate degree-d polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can be computed by an arithmetic circuit of size at most poly(s,n,d).