4 papers · 1 filter
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…
The Existential Theory of the Reals with Summation Operators
Markus Bläser, Julian Dörfler, Maciej Liskiewicz +1
To characterize the computational complexity of satisfiability problems for probabilistic and causal reasoning within the Pearl's Causal Hierarchy, arXiv:2305.09508 [cs.AI] introdu…