Stefan Szeider

Stefan Szeider
NationalityAustrian
Alma materUniversity of Vienna
Scientific career
FieldsAlgorithms
Complexity
Theoretical computer science
Boolean satisfiability
Constraint satisfaction
Parameterized complexity
InstitutionsTU Wien
University of Durham
University of Toronto
Austrian Academy of Sciences
Doctoral advisorsHerbert Fleischner
Georg Gottlob

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]

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.[4][5]

Career and research

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]

References

  1. ^ a b "Faculty of Informatics, TU Wien". Retrieved 13 January 2017.
  2. ^ "Stefan Szeider - Algorithms and Complexity Group". Retrieved 9 January 2017.
  3. ^ "Computerwissenschafter der TU Wien wollen internationale Marke werden". Der Standard (in German). 25 January 2012. Retrieved 20 April 2020.
  4. ^ "Stefan Szeider - The Mathematics Genealogy Project". Mathematics Genealogy Project. Retrieved 9 January 2017.
  5. ^ a b c "Stefan Szeider". LogiCS. Retrieved 9 January 2017.
  6. ^ "What does "insoluble" mean here? Prof. Stefan Szeider in portrait". Retrieved 13 January 2017.
  7. ^ "Algorithmen bestimmen unser Leben". Futurezone.at (in German). February 8, 2012. Retrieved 9 January 2017.
  8. ^ "Zentrum für Grundlagen der Informatik". Der Standard (in German). 31 January 2012. Retrieved 9 January 2017.
  9. ^ "Stefan Szeider - Professor, Head of Algorithms and Complexity Group, TU Wien". Google Scholar. Retrieved 9 January 2017.
  10. ^ "Stefan Szeider - Computer Science Bibliography". DBLP.
  11. ^ Gaspers, Serge; Szeider, Stefan (2012). "Backdoors to Satisfaction". The Multivariate Algorithmic Revolution and Beyond. Lecture Notes in Computer Science. Vol. 7370. pp. 287–317. CiteSeerX 10.1.1.747.5422. doi:10.1007/978-3-642-30891-8_15. ISBN 978-3-642-30890-1. S2CID 6905561.
  12. ^ Gaspers, Serge (22 April 2016). "Backdoors to SAT". Encyclopedia of Algorithms. Springer New York. pp. 167–170. doi:10.1007/978-1-4939-2864-4_781. ISBN 978-1-4939-2863-7.{{cite book}}: CS1 maint: location missing publisher (link)
  13. ^ Samer, Marko; Szeider, Stefan (18 December 2008). "Backdoor Sets of Quantified Boolean Formulas". Journal of Automated Reasoning. 42 (1): 77–97. CiteSeerX 10.1.1.452.5953. doi:10.1007/s10817-008-9114-5. S2CID 13030704.
  14. ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (January 2009). "Clique-Width is NP-Complete". SIAM Journal on Discrete Mathematics. 23 (2): 909–939. doi:10.1137/070687256.
  15. ^ Szeider, Stefan (December 2004). "Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable" (PDF). Journal of Computer and System Sciences. 69 (4): 656–674. doi:10.1016/j.jcss.2004.04.009.
  16. ^ Fleischner, Herbert; Kullmann, Oliver; Szeider, Stefan (October 2002). "Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference". Theoretical Computer Science. 289 (1): 503–516. doi:10.1016/S0304-3975(01)00337-1.