Fast Exact Algorithms Using Hadamard Product of Polynomials
share
In this paper we develop an efficient procedure for computing a (scaled) Hadamard product for commutative polynomials. This serves as a tool to obtain faster algorithms for several problems. Our main algorithmic results include the following: 1) Given an arithmetic circuit C of poly(n) size computing a polynomial f∈F[X] and a parameter k, we give a deterministic algorithm of run time O^*(n^k/2+c k) for some constant c to compute the sum of the coefficients of multilinear monomials of degree k in f, that answers an open question mentioned by Koutis and Williams in KW16. 2) Given an arithmetic circuit C of size s computing a polynomial f∈F[X] (where F could be any field where the field arithmetic is efficient), and a parameter k, we give a randomized algorithm of run time 4.32^k·poly(n,s) to check if f contains a multilinear monomial of degree k or not. Our algorithm uses poly(n,k,s) space. The recent algorithm of Brand et al. BDH18 solves this problem over fields of characteristic zero using exterior algebra. 3) If the given circuit C is a depth-three homogeneous circuit computing f ∈Q[X] of degree k, we give a deterministic parameterized algorithm of run time 4^k ·poly(n,s) to detect degree k multilinear terms, and an algorithm of run time 2^k ·poly(n,s) to compute the sum of their coefficients in f. For finite fields also we can detect degree k multilinear terms in f in deterministic e^k k^O( k)(2^ck + 2^k)·poly(n,s) time for c≤ 5.
READ FULL TEXT