1 Search Results for "Röyskö, Antti"


Document
Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs

Authors: Mikko Koivisto and Antti Röyskö

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)


Abstract
The zeta and Moebius transforms over the subset lattice of n elements and the so-called subset convolution are examples of unary and binary operations on set functions. While their direct computation requires O(3ⁿ) arithmetic operations, less naive algorithms only use 2ⁿ poly(n) operations, nearly linear in the input size. Here, we investigate a related n-ary operation that takes n set functions as input and maps them to a new set function. This operation, we call multi-subset transform, is the core ingredient in the known inclusion - exclusion recurrence for weighted sums over acyclic digraphs, which extends Robinson’s recurrence for the number of labelled acyclic digraphs. Prior to this work, the best known complexity bound for computing the multi-subset transform was the direct O(3ⁿ). By reducing the task to rectangular matrix multiplication, we improve the complexity to O(2.985ⁿ).

Cite as

Mikko Koivisto and Antti Röyskö. Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{koivisto_et_al:LIPIcs.SWAT.2020.29,
  author =	{Koivisto, Mikko and R\"{o}ysk\"{o}, Antti},
  title =	{{Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{29:1--29:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.29},
  URN =		{urn:nbn:de:0030-drops-122768},
  doi =		{10.4230/LIPIcs.SWAT.2020.29},
  annote =	{Keywords: Bayesian networks, Moebius transform, Rectangular matrix multiplication, Subset convolution, Weighted counting of acyclic digraphs, Zeta transform}
}
  • Refine by Author
  • 1 Koivisto, Mikko
  • 1 Röyskö, Antti

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Bayesian networks
  • 1 Moebius transform
  • 1 Rectangular matrix multiplication
  • 1 Subset convolution
  • 1 Weighted counting of acyclic digraphs
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail