Model Counting: Solving, Complexity, and Applications

Speaker(s)

Johannes Fichte

Affiliation

Linköping University

Language of the talk

English

Date

May 14, 2026, 12:15 p.m.

Room

room 4060

Seminar

Seminar Algorithmic Economics

---

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.

---