Search Results

Documents authored by Peterseim, Benedikt

Document
DOI: 10.4230/LIPIcs.LICS.2026.76
Fixed-Parameter Tractable Inference for Discrete Probabilistic Programs, via String Diagram Algebraisation

Authors: Benedikt Peterseim and Milan Lopuhaä-Zwakenberg

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
Discrete probabilistic programs (DPPs) provide a highly expressive formalism for compactly defining arbitrary finite probabilistic models. This expressivity comes at a price: DPP inference is PSPACE-hard. In this work, we show that DPP inference only takes polynomial time for programs that are "structurally simple". More precisely, inference can be performed in polynomial time when the primal graph of each function appearing in the probabilistic program has bounded treewidth, and the inverse acceptance probability is at most exponential in the size of the probabilistic program. Existing algorithms do not achieve this performance guarantee. Our method relies on finding suitable decompositions, algebraisations, of the string diagrams underlying DPPs, employing existing algorithms for tree decompositions. This is independent of the probabilistic setting of DPPs and has direct applications to many problems, such as evaluating queries on relational databases and cybersecurity risk assessment via attack trees.
Cite as

Benedikt Peterseim and Milan Lopuhaä-Zwakenberg. Fixed-Parameter Tractable Inference for Discrete Probabilistic Programs, via String Diagram Algebraisation. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 76:1-76:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{peterseim_et_al:LIPIcs.LICS.2026.76,
  author =	{Peterseim, Benedikt and Lopuha\"{a}-Zwakenberg, Milan},
  title =	{{Fixed-Parameter Tractable Inference for Discrete Probabilistic Programs, via String Diagram Algebraisation}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{76:1--76:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.76},
  URN =		{urn:nbn:de:0030-drops-268637},
  doi =		{10.4230/LIPIcs.LICS.2026.76},
  annote =	{Keywords: probabilistic programming, string diagrams, treewidth, fixed-parameter tractability, probabilistic inference, parameterised complexity, hypergraph categories}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact