stringtranslate.com

Stefan Szeider

Stefan Szeider es un informático austríaco que trabaja en las áreas de algoritmos , complejidad computacional , informática teórica y, más específicamente, en satisfacibilidad proposicional , problemas de satisfacción de restricciones y complejidad parametrizada . Es profesor titular en la Facultad de Informática [1] de la Universidad Tecnológica de Viena (TU Wien), director del Grupo de Algoritmos y Complejidad y copresidente del Centro de Viena para la Lógica y los Algoritmos (VCLA) de la TU Wien. [2] [3]

Educación

Szeider recibió su doctorado en Matemáticas de la Universidad de Viena en 2001 bajo la supervisión de los profesores Herbert Fleischner y Georg Gottlob mientras trabajaba como matemático en la Academia Austriaca de Ciencias . [4] [5]

Carrera e investigación

Szeider es profesor titular en la Facultad de Informática de la TU Wien . [1] Anteriormente fue primero profesor y luego lector en la Universidad de Durham , Reino Unido (2004-2009) y posdoctorado en el Grupo del Profesor Stephen Cook en la Universidad de Toronto (2002-2004). [5] [6] Es copresidente del Centro de Lógica y Algoritmos de Viena, que fundó junto con Helmut Veith en 2012. [7] [8] Forma parte de los consejos editoriales del Journal of Computer and System Sciences , el Journal of Discrete Algorithms , el Journal of Artificial Intelligence Research y Fundamenta Informaticae . [5]

Szeider publicó más de 140 publicaciones arbitradas en las áreas de informática teórica, algoritmos, complejidad computacional, inteligencia artificial, satisfacibilidad proposicional y satisfacción de restricciones. [9] [10]

Szeider es más conocido por popularizar la noción de conjuntos de puerta trasera para SAT y otros problemas [11] [12] y la introducción de esquemas de dependencia para fórmulas booleanas cuantificadas . [13]

Szeider también trabajó en medidas de ancho para gráficos como el ancho de árbol y el ancho de camarilla . Demostró con coautores que es NP-difícil determinar si el ancho de camarilla de un gráfico dado es menor que un límite dado. [14] Estableció resultados de complejidad para detectar fórmulas mínimamente insatisfactorias . [15] [16]

Referencias

  1. ^ ab "Facultad de Informática, TU Wien" . Consultado el 13 de enero de 2017 .
  2. ^ "Stefan Szeider - Grupo de Algoritmos y Complejidad" . Consultado el 9 de enero de 2017 .
  3. ^ "Computerwissenschafter der TU Wien wollen internationale Marke werden". Der Standard (en alemán) . 25 de enero de 2012 . Consultado el 20 de abril de 2020 .
  4. ^ "Stefan Szeider - El proyecto de genealogía matemática". Proyecto de genealogía matemática . Consultado el 9 de enero de 2017 .
  5. ^ abc "Stefan Szeider". LogiCS . Consultado el 9 de enero de 2017 .
  6. ^ "¿Qué significa aquí "insoluble"? El profesor Stefan Szeider en un retrato" . Consultado el 13 de enero de 2017 .
  7. ^ "Algoritmos bestimmen unser Leben". Futurezone.at (en alemán). 8 de febrero de 2012 . Consultado el 9 de enero de 2017 .
  8. ^ "Zentrum für Grundlagen der Informatik". Der Standard (en alemán). 31 de enero de 2012 . Consultado el 9 de enero de 2017 .
  9. ^ "Stefan Szeider - Profesor, Jefe del Grupo de Algoritmos y Complejidad, TU Wien". Google Scholar . Consultado el 9 de enero de 2017 .
  10. ^ "Stefan Szeider - Bibliografía sobre informática". DBLP .
  11. ^ Gaspers, Serge; Szeider, Stefan (2012). "Puertas traseras a la satisfacción". La revolución algorítmica multivariante y más allá . Apuntes de clase en informática. Vol. 7370. págs. 287–317. CiteSeerX 10.1.1.747.5422 . doi :10.1007/978-3-642-30891-8_15. ISBN .  978-3-642-30890-1.S2CID6905561  .​
  12. ^ Gaspers, Serge (22 de abril de 2016). "Backdoors to SAT". Enciclopedia de algoritmos . Springer Nueva York. págs. 167-170. doi :10.1007/978-1-4939-2864-4_781. ISBN 978-1-4939-2863-7.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
  13. ^ Samer, Marko; Szeider, Stefan (18 de diciembre de 2008). "Conjuntos de puerta trasera de fórmulas booleanas cuantificadas". Revista de razonamiento automatizado . 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 (enero de 2009). "El ancho de camarilla es NP-completo". Revista SIAM de Matemáticas Discretas . 23 (2): 909–939. doi :10.1137/070687256.
  15. ^ Szeider, Stefan (diciembre de 2004). "Las fórmulas mínimas insatisfactorias con una diferencia entre cláusulas y variables acotadas son manejables con parámetros fijos" (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 (octubre de 2002). "Reconocimiento en tiempo polinomial de fórmulas mínimas insatisfactorias con diferencia fija entre cláusula y variable". Ciencias de la Computación Teórica . 289 (1): 503–516. doi : 10.1016/S0304-3975(01)00337-1 .

Enlaces externos