Arvind, V. ;
Chatterjee, Abhranil ;
Datta, Rajit ;
Mukhopadhyay, Partha
Fast Exact Algorithms Using Hadamard Product of Polynomials
Abstract
Let C be an arithmetic circuit of poly(n) size given as input that computes a polynomial f in F[X], where X={x_1,x_2,...,x_n} and 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 [Ioannis Koutis, 2008; Ryan Williams, 2009; Ioannis Koutis and Ryan Williams, 2016].
 (k,n)MLC: Compute the sum of the coefficients of all degreek multilinear monomials in the polynomial f.
 kMMD: Test if there is a nonzero degreek multilinear monomial in the polynomial f.
Our algorithms are based on the fact that the Hadamard product f o S_{n,k}, is the degreek multilinear part of f, where S_{n,k} is the k^{th} elementary symmetric polynomial.
 For (k,n)MLC problem, we give a deterministic algorithm of run time O^*(n^(k/2+c log k)) (where c is a constant), answering an open question of Koutis and Williams [Ioannis Koutis and Ryan Williams, 2016]. As corollaries, we show O^*(binom{n}{downarrow k/2})time exact counting algorithms for several combinatorial problems: kTree, tDominating Set, mDimensional kMatching.
 For kMMD problem, we give a randomized algorithm of run time 4.32^k * poly(n,k). Our algorithm uses only poly(n,k) space. This matches the run time of a recent algorithm [Cornelius Brand et al., 2018] for kMMD which requires exponential (in k) space.
Other results include fast deterministic algorithms for (k,n)MLC and kMMD problems for depth three circuits.
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs:2019:11571,
author = {V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay},
title = {{Fast Exact Algorithms Using Hadamard Product of Polynomials}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {9:19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771313},
ISSN = {18688969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11571},
URN = {urn:nbn:de:0030drops115711},
doi = {10.4230/LIPIcs.FSTTCS.2019.9},
annote = {Keywords: Hadamard Product, Multilinear Monomial Detection and Counting, Rectangular Permanent, Symmetric Polynomial}
}
04.12.2019
Keywords: 

Hadamard Product, Multilinear Monomial Detection and Counting, Rectangular Permanent, Symmetric Polynomial 
Seminar: 

39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 