| Stefan Szeider | |
| Nationality: | Austrian |
| Fields: | Algorithms Complexity Theoretical computer science Boolean satisfiability Constraint satisfaction Parameterized complexity |
| Workplaces: | TU Wien University of Durham University of Toronto Austrian Academy of Sciences |
| Alma Mater: | University of Vienna |
| Thesis1 Title: | and |
| Thesis2 Title: | )--> |
| Thesis1 Url: | and |
| Thesis2 Url: | )--> |
| Thesis1 Year: | and |
| Thesis2 Year: | )--> |
| Spouses: | )--> |
| Partners: | )--> |
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[1] 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.[2] [3]
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.[4] [5]
Szeider is a full professor at the Faculty of Informatics at TU Wien.[1] Previously he was first Lecturer and then Reader at the University of Durham, UK (2004–2009) and a postdoc with Professor Stephen Cook’s Group at the University of Toronto (2002–2004).[5] [6] He is a co-chair of the Vienna Center for Logic and Algorithms, which he founded together with Helmut Veith in 2012.[7] [8] 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.[5]
Szeider published more than 140 refereed publications in the areas of theoretical computer science, algorithms, computational complexity, artificial intelligence, propositional satisfiability and constraint satisfaction.[9] [10]
Szeider is best known for popularizing the notion of backdoor sets for SAT and other problems[11] [12] and the introduction of dependency schemes for quantified boolean formulas.[13]
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.[14] He established complexity results for detecting minimally unsatisfiable formulas.[15] [16]