Fast Exact Algorithms Using Hadamard Product of Polynomials

Let $C$ be an arithmetic circuit of $poly(n)$ size given as input that computes a polynomial $f\in \mathbb{F}[X]$, where $X=\{x_1,x_2,\dots ,x_n\}$ and $\mathbb{F}$ is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams \cite{Kou08, Wi09, KW16}. k-MLC: Compute the sum of the coefficients of all degree-$k$ multilinear monomials in the polynomial $f$. k-MMD: Test if there is a nonzero degree-$k$ multilinear monomial in the polynomial $f$. Our algorithms are based on the fact that the Hadamard product $f\circ S_{n,k}$,isthedegree-$k$multilinearpartof$f$,where$S_{n,k}$isthe$k^{th}$ elementary symmetric polynomial.

1. For k-MLC problem, we give a deterministic algorithm of run time $O^{\ast }(n^{k\mathrm{/}2+c\log k})$ (where $c$ is a constant), answering an open question of Koutis and Williams \cite[ICALP’09]{KW16}. As corollaries, we show $O^{\ast }(\left(\genfrac{}{}{0px}{}{n}{\downarrow k\mathrm{/}2}\right))$-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching.
2. For k-MMD problem, we give a randomized algorithm of run time $4.32^k\cdot poly(n,k)$\mathrm{.}Ouralgorithmusesonly$poly(n,k)$ space. This matches the run time of a recent algorithm \cite{BDH18} for $k-MMD$ which requires exponential (in $k$) space. Other results include fast deterministic algorithms for k-MLC and k-MMD problems for depth three circuits.