4 papers
The Complexity of Bisimilarity and Model Checking in Finitary Diagrams
Markus Bläser, Sagnik Dutta, Samuel Okyay
Inspired by the work of Dubut, Goubault, and Goubault-Larrecq (ICALP 2015) on natural homology, Dubut (RAMiCS 2020) introduces finitary diagrams and studies bisimilarity and diagra…
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
Markus Bläser, Sagnik Dutta, Gorav Jindal
Efficient algorithms for many problems in optimization and computational algebra often arise from casting them as systems of polynomial equations. Blum, Shub, and Smale formalized…
Which graph motif parameters count?
Markus Bläser, Radu Curticapean, Julian Dörfler +1
For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interp…
Probabilistic and Causal Satisfiability: Constraining the Model
Markus Bläser, Julian Dörfler, Maciej LiÅkiewicz +1
We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables over finite domains, the basic terms are probabil…