Institut für Theoretische Informatik

Dr. Simon Straub

Interessen

  • Im Allgemeinen: Komplexitätstheorie
  • Im Speziellen: Parallele Komplexität
  • Und davon besonders: Matchings

Lehre

  • Kryptologie: Algorithmen und Methoden (SS16)
  • Grundlagen der Mathematik (WS15/16, HS Aalen)
  • Formale Grundlagen der Informatik (WS15/16)
  • Algorithmen und Datenstrukturen (WS15/16)
  • Einführung in die Informatik / Praktische Informatik (SS15)
  • Algorithmen und Datenstrukturen (WS14/15)
  • Proseminar Algorithmen (WS14/15)
  • Berechenbarkeit und Komplexität (SS14)
  • Logik (SS14)
  • Formale Grundlagen der Informatik (WS13/14)
  • Proseminar Algorithmen (WS13/14)
  • Berechenbarkeit und Komplexität (SS13)
  • Proseminar Klassiker der Informatik (SS13)
  • Formale Grundlagen der Informatik (WS12/13)
  • Proseminar Algorithmen (WS12/13)
  • Logik (SS12)
  • Projekt Implementierung von web-Suchmaschinen (WS11/12)
  • Algorithmen und Datenstrukturen (WS11/12)
  • Logik (SS11)
  • Seminar Algorithmen in der Graphentheorie (SS11)
  • Algorithmen und Datenstrukturen (WS10/11)

Publikationen

  • S. Straub. Gadgets for Perfect Matching Problems. Dissertation. Universität Ulm, 2015.
  • S. Straub, T. Thierauf, and F. Wagner. Counting the Number of Perfect Matchings in $K_5$-free Graphs.  Theory of Computing Systems, 1–24, 2015. First online: 15 July 2015. Doi 10.1007/s00224-015-9645-1.
    siehe auch: IEEE Conference on Computational Complexity (CCC), 66-77, 2014. Doi 10.1109/CCC.2014.15.
    siehe auch: Technical Report TR14-079, Electronic Colloquium on Computational Complexity, 2014.ECCC TR14-079
  • R. Gurjar, A. Korwar, J. Messner, S. Straub, and T. Thierauf.  Planarizing Gadgets for Perfect Matching Do Not Exist. In  Rovan, B., Sassone, V., and Widmayer, P., editors, Mathematical Foundations of Computer Science 2012,  volume 7464 of Lecture Notes in Computer Science, pages 478-490. Springer Berlin Heidelberg, 2012. Doi 10.1007/978-3-642-32589-2_43.
    siehe auch: Technical Report TR11-148, Electronic Colloquium on Computational Complexity, 2011.ECCC TR11-148
    siehe dazu auch: Beitrag im Computational Complexity Blog von Lance Fortnow und Bill Gasarch