Talks and Poster Presentations (without Proceedings-Entry):

S. Szeider:
"Capturing Structure in SAT and Related Problems";
Keynote Lecture: International Workshop on Graph Structure and Satisfiability Testing, Bordeaux, France (invited); 2016-07-04.

English abstract:
Propositional satisfiability (SAT) and related problems (like Model Counting, QBF-SAT, and CSP) are in practise often much easier to solve than suggested by their respective theoretical worst-case complexities. This "friendliness" of the real world is often explained by the presence of some kind of "hidden structure" in practical problem instances. In this talk we will review some mathematical concepts that attempt to capture the structure in problem instances and discuss their virtues and limits. We will focus rather on general questions than on technical details.

Created from the Publication Database of the Vienna University of Technology.