Biography:Stefan Szeider

From HandWiki
Revision as of 07:59, 7 February 2024 by JStaso (talk | contribs) (update)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: Austrian computer scientist
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. 1.0 1.1 "Faculty of Informatics, TU Wien". http://www.informatik.tuwien.ac.at/english. 
  2. "Stefan Szeider - Algorithms and Complexity Group". https://www.ac.tuwien.ac.at/people/szeider/. 
  3. "Computerwissenschafter der TU Wien wollen internationale Marke werden". Der Standard (in German). 25 January 2012. https://www.derstandard.at/story/1326503675233/computerwissenschafter-der-tu-wien-wollen-internationale-marke-werden. 
  4. "Stefan Szeider - The Mathematics Genealogy Project". Mathematics Genealogy Project. https://www.genealogy.math.ndsu.nodak.edu/id.php?id=139662. 
  5. 5.0 5.1 5.2 "Stefan Szeider". http://logic-cs.at/faculty/stefan-szeider/. 
  6. "What does "insoluble" mean here? Prof. Stefan Szeider in portrait". https://translate.google.com/translate?sl=auto&tl=en&js=y&prev=_t&hl=en&ie=UTF-8&u=https%3A%2F%2Fwww.tuwien.ac.at%2Faktuelles%2Fnews_detail%2Farticle%2F7322%2F&edit-text=. 
  7. "Algorithmen bestimmen unser Leben" (in de). Futurezone.at. February 8, 2012. https://futurezone.at/science/algorithmen-bestimmen-unser-leben/24.576.366. 
  8. "Zentrum für Grundlagen der Informatik" (in de). Der Standard. 31 January 2012. http://derstandard.at/1326504261313/Zentrum-fuer-Grundlagen-der-Informatik. 
  9. "Stefan Szeider - Professor, Head of Algorithms and Complexity Group, TU Wien". https://scholar.google.com/citations?user=lJYKhNIAAAAJ. 
  10. "Stefan Szeider - Computer Science Bibliography". http://dblp.uni-trier.de/pers/hd/s/Szeider:Stefan. 
  11. Gaspers, Serge; Szeider, Stefan (2012). "Backdoors to Satisfaction". The Multivariate Algorithmic Revolution and Beyond. Lecture Notes in Computer Science. 7370. pp. 287–317. doi:10.1007/978-3-642-30891-8_15. ISBN 978-3-642-30890-1. 
  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. 
  13. Samer, Marko; Szeider, Stefan (18 December 2008). "Backdoor Sets of Quantified Boolean Formulas". Journal of Automated Reasoning 42 (1): 77–97. doi:10.1007/s10817-008-9114-5. 
  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". Journal of Computer and System Sciences 69 (4): 656–674. doi:10.1016/j.jcss.2004.04.009. http://dro.dur.ac.uk/610/1/610.pdf. 
  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. 

External links