2026-07-20T07:29:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11571 2024-03-06T10:48:20Z ddc:004 open_access

Fast Exact Algorithms Using Hadamard Product of Polynomials Arvind, V. Chatterjee, Abhranil Datta, Rajit Mukhopadhyay, Partha Hadamard Product Multilinear Monomial Detection and Counting Rectangular Permanent Symmetric Polynomial 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 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 o S_{n,k}, is the degree-k 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: k-Tree, t-Dominating Set, m-Dimensional k-Matching. - For k-MMD 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 k-MMD which requires exponential (in k) space. Other results include fast deterministic algorithms for (k,n)-MLC and k-MMD problems for depth three circuits. Schloss Dagstuhl – Leibniz-Zentrum für Informatik V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.9 urn:nbn:de:0030-drops-115711 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.9 eng https://creativecommons.org/licenses/by/3.0/legalcode