Abstract
We present 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 results are: 1) Given an arithmetic circuit C over rationals or finite fields, and a parameter k, we give a deterministic algorithm of run time n^(k/2+clogk) for some constant c to compute the sum of the coefficients of multilinear monomials of degree k in f. 2) Given an arithmetic circuit C over rationals or finite fields, and a parameter k, we give a randomized algorithm of run time O^*(4.32^k) to check if f contains a multilinear monomial of degree k. Our algorithm uses polynomial space. This is joint work with Abhranil Chatterjee, Raji Datta, and Partha Mukhopadhyay.