Stefan Szeider

Stefan Szeider is an Austrian computer scientist who works on the areas of algorithms, computational complexity, theoretical computer science, and more specifically on propositional satisfiability, constraint satisfaction problems, and parameterised complexity. He is a full professor at the Faculty of Informatics at the Vienna University of Technology (TU Wien), the head of the Algorithms and Complexity Group, and co-chair of the Vienna Center for Logic and Algorithms (VCLA) of TU Wien.

Education Szeider received his doctorate in Mathematics from the University of Vienna in 2001 under the supervision of Professors Herbert Fleischner and Georg Gottlob while working as a mathematician at the Austrian Academy of Sciences.

Career and research Szeider is a full professor at the Faculty of Informatics at TU Wien. He is a co-chair of the Vienna Center for Logic and Algorithms, which he founded together with Helmut Veith in 2012. He serves on the editorial boards of the Journal of Computer and System Sciences, the Journal of Discrete Algorithms, the Journal of Artificial Intelligence Research and Fundamenta Informaticae.

Szeider is best known for popularizing the notion of backdoor sets for SAT and other problems and the introduction of dependency schemes for quantified boolean formulas.

Szeider also worked on width measures for graphs such as treewidth and clique-width. He showed with coauthors that it is NP-hard to determine whether the clique-width of a given graph is smaller than a given bound. He established complexity results for detecting minimally unsatisfiable formulas.