EUVIMEDEUVIMED entdecken
Crossref

Fast Exact Algorithms Using Hadamard Product of Polynomials

V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Algorithmica · 2022-02 · 84 (2) · 436-463

DOI: 10.1007/s00453-021-00900-0 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 10.01.2022. Verfasst von V. Arvind und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 42 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let C be an arithmetic circuit of size s, given as input that computes a polynomial f∈F[x1,x2,…,xn]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f\in {\mathbb {F}}[x_1,x_2,\ldots ,x_n]$$\end{document}, where F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {F}}$$\end{document} is a finite field or the field of rationals. Using the Hadamard product of polynomials, we obtain new algorithms for the following two problems first studied by Koutis and Williams (Faster algebraic algorithms for path and packing problems, 2008, https://doi.org/10.1007/978-3-540-70575-8_47; ACM Trans Algorithms 12(3):31:1–31:18, 2016, https://doi.org/10.1145/2885499; Inf Process Lett 109(6):315–318, 2009, https://doi.org/10.1016/j.ipl.2008.11.004): (k,n)-MLC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{(\textit{k,n}){-}\mathrm{M{L}\normalsize {C}}}}}$$\end{document}: is the problem of computing the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. We obtain a deterministic algorithm of running time n↓k/2·nO(logk)·sO(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n\atopwithdelims (){\downarrow k/2}}\cdot n^{O(\log k)}\cdot s^{O(1)}$$\end{document}. This improvement over the O(nk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^k)$$\end{document} time brute-force search algorithm answers positively a question of Koutis and Williams (2016). As applications, we give exact counting algorithms, faster than brute-force search, for counting the number of copies of a tree of size k in a graph, and also the problem of exact counting of m-dimensional k-matchings. k-MMD\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\textit{k}{-}\mathrm{M{M}\normalsize {D}}}}}$$\end{document}: is the problem of checking if there is a degree-k multilinear monomial in the polynomial f with non-zero coefficient. We obtain a randomized algorithm of running time O(4.32k·nO(1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(4.32^k\cdot n^{O(1)})$$\end{document}. Additionally, our algorithm is polynomial space bounded. Other results include fast deterministic algorithms for (k,n)-MLC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{(\textit{k,n}){-}\mathrm{M{L}\normalsize {C}}}}}$$\end{document} and k-MMD\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\textit{k}{-}\mathrm{M{M}\normalsize {D}}}}}$$\end{document} problems for depth three circuits. (k,n)-MLC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{(\textit{k,n}){-}\mathrm{M{L}\normalsize {C}}}}}$$\end{document}: is the problem of computing the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. We obtain a deterministic algorithm of running time n↓k/2·nO(logk)·sO(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n\atopwithdelims (){\downarrow k/2}}\cdot n^{O(\log k)}\cdot s^{O(1)}$$\end{document}. This improvement over the O(nk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^k)$$\end{document} time brute-force search algorithm answers positively a question of Koutis and Williams (2016). As applications, we give exact counting algorithms, faster than brute-force search, for counting the number of copies of a tree of size k in a graph, and also the problem of exact counting of m-dimensional k-matchings. k-MMD\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\textit{k}{-}\mathrm{M{M}\normalsize {D}}}}}$$\end{document}: is the problem of checking if there is a degree-k multilinear monomial in the polynomial f with non-zero coefficient. We obtain a randomized algorithm of running time O(4.32k·nO(1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(4.32^k\cdot n^{O(1)})$$\end{document}. Additionally, our algorithm is polynomial space bounded.

Zitieren

APA

Arvind, V., Chatterjee, A., Datta, R., & Mukhopadhyay, P. (2022). Fast Exact Algorithms Using Hadamard Product of Polynomials. Algorithmica, 84(2), 436-463. https://doi.org/10.1007/s00453-021-00900-0

Vancouver

Arvind V, Chatterjee A, Datta R, Mukhopadhyay P. Fast Exact Algorithms Using Hadamard Product of Polynomials. Algorithmica. 2022;84(2):436-463. doi:10.1007/s00453-021-00900-0

BibTeX
@article{Arvind2022,
  author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
  title = {Fast Exact Algorithms Using Hadamard Product of Polynomials},
  journal = {Algorithmica},
  year = {2022},
  volume = {84},
  number = {2},
  pages = {436--463},
  doi = {10.1007/s00453-021-00900-0}
}
Kostenlos starten →