Stefan Szeider - Stefan Szeider - Wikipedia

Stefan Szeider
Národnostrakouský
Alma materVídeňská univerzita
Vědecká kariéra
PoleAlgoritmy
Složitost
Teoretická informatika
Booleovská uspokojivost
Omezení spokojenosti
Parametrizovaná složitost
InstituceTU Wien
University of Durham
University of Toronto
Rakouská akademie věd
Doktorští poradciHerbert Fleischner
Georg Gottlob

Stefan Szeider je rakouský počítačový vědec, který pracuje v oblastech algoritmy, výpočetní složitost, teoretická informatika a konkrétněji na výroková uspokojivost, problémy s uspokojením omezení, a parametrizovaná složitost. Je řádným profesorem na Fakultě informatiky[1] na Vídeňská technická univerzita (TU Wien), vedoucí skupiny Algorithms and Complexity Group, a spolupředseda Vídeňské centrum logiky a algoritmů TU Wien (VCLA).[2][3]

Vzdělávání

Szeider získal doktorát z matematiky na vídeňské univerzitě v roce 2001 pod vedením profesorů Herberta Fleischnera a Georg Gottlob zatímco pracuje jako matematik na Rakouská akademie věd.[4][5]

Kariéra a výzkum

Szeider je plný profesor na Fakultě informatiky v TU Wien.[1] Dříve působil nejprve jako lektor a poté jako čtenář na University of Durham, Velká Británie (2004-2009) a postdoktorand s profesorem Stephen Cook Group na University of Toronto (2002-2004).[5][6] Je spolupředsedou vídeňského Centra pro logiku a algoritmy, které založil společně Helmut Veith v roce 2012.[7][8] Působí v redakčních radách Journal of Computer and System Sciences Journal of Discrete Algorithms, Journal of Artificial Intelligence Research a Fundamenta Informaticae.[5]

Szeider publikoval více než 140 recenzovaných publikací v oblasti teoretické informatiky, algoritmů, výpočetní složitosti, umělé inteligence, výrokové uspokojivosti a omezení.[9][10]

Szeider je nejlépe známý tím, že popularizuje představu sad backdoor pro SAT a další problémy[11][12] a zavedení systémů závislostí pro kvantifikované booleovské vzorce.[13]

Szeider také pracoval na šířkových měřítcích pro grafy, jako jsou šířka stromu a šířka kliky. U spoluautorů ukázal, že je NP-těžké určit, zda je šířka kliky daného grafu menší než daná mez.[14] Zjistil výsledky složitosti pro detekci minimálně neuspokojivé vzorce.[15][16]

Reference

  1. ^ A b „Fakulta informatiky TU Wien“. Citováno 13. ledna 2017.
  2. ^ „Stefan Szeider - Algorithms and Complexity Group“. Citováno 9. ledna 2017.
  3. ^ „Computerwissenschafter der TU Wien wollen internationalation Marke werden“. Der Standard (v němčině). 25. ledna 2012. Citováno 20. dubna 2020.
  4. ^ „Stefan Szeider - Matematický genealogický projekt“. Matematický genealogický projekt. Citováno 9. ledna 2017.
  5. ^ A b C „Stefan Szeider“. LogiCS. Citováno 9. ledna 2017.
  6. ^ „Co zde znamená„ nerozpustný “? Portrét prof. Stefana Szeidera“. Citováno 13. ledna 2017.
  7. ^ „Algorithmen bestimmen unser Leben“. Futurezone.at (v němčině). 8. února 2012. Citováno 9. ledna 2017.
  8. ^ „Zentrum für Grundlagen der Informatik“. Der Standard (v němčině). 31. ledna 2012. Citováno 9. ledna 2017.
  9. ^ „Stefan Szeider - profesor, vedoucí skupiny Algorithms and Complexity Group, TU Wien“. Google Scholar. Citováno 9. ledna 2017.
  10. ^ „Stefan Szeider - Computer Science Bibliography“. DBLP.
  11. ^ Gaspers, Serge; Szeider, Stefan (2012). "Multivariační algoritmická revoluce a další". Zadní vrátka k spokojenosti. 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. dubna 2016). "Zadní vrátka do SAT". Encyclopedia of Algorithms. Springer New York. 167–170. doi:10.1007/978-1-4939-2864-4_781. ISBN  978-1-4939-2863-7.
  13. ^ Samer, Marko; Szeider, Stefan (18. prosince 2008). "Backdoorové sady kvantifikovaných booleovských vzorců". 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 (leden 2009). "Clique-Width je NP-Complete". SIAM Journal on Discrete Mathematics. 23 (2): 909–939. doi:10.1137/070687256.
  15. ^ Szeider, Stefan (prosinec 2004). „Minimální neuspokojivé vzorce s rozdílem rozdílu klauzule-proměnná jsou fixovatelné pomocí parametru“ (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 (říjen 2002). Msgstr "Rozpoznání polynomiálního času minimálních neuspokojivých vzorců s pevným rozdílem klauzule - proměnná". Teoretická informatika. 289 (1): 503–516. doi:10.1016 / S0304-3975 (01) 00337-1.

externí odkazy