Abhranil Chatterjee: The Arithmetic Complexity of S_n,k^* and Multilinear Monomial Counting and Detection

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.

This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.