Model Counting: Solving, Complexity, and Applications

Prelegent(ci)

Johannes Fichte

Afiliacja

Linköping University

Język referatu

angielski

Termin

14 maja 2026 12:15

Pokój

p. 4060

Seminarium

Seminarium „Ekonomia algorytmiczna”

---

In this talk, I will consider model counting, which asks to output the number of solutions to a given input instance. I will present recent complexity results and a solving approach that employs structural parameters (treewidth) for faster solving. While the algorithm provides a theoretical bound, a direct implementation is, unsurprisingly, practically infeasible. Therefore, we turn our attention to a more practical exploitable direction. Finally, I will illustrate practical applications of counting to analyze and navigate solution spaces, including directions that focus on counting for decision spaces rather than entire solution spaces, significantly improving complexity.

---