Institut für Theoretische Informatik

Dr. Fabian Wagner

Interessen

  • Isomorphieprobleme auf Graphen und algebraischen Strukturen
  • Komplexitätstheorie
  • Graphentheorie

Lehre

  • Seminar: Algorithmen in der Graphentheorie (SS 2007)
  • Tutorium: Formale Grundlagen der Informatik (WS 2007/08)
  • Übungen: Komplexitätstheorie (SS 2008)
  • Übungen: Berechenbarkeit und Komplexität (SS2010)
  • Übungen: Logik (SS2010)
  • Seminar: Algorithmen in der Graphentheorie (SS2010)
  • Übungen: Formale Grundlagen der Informatik (WS2010/11)
  • Seminar: Probleme in NP (WS2010/11)

Seminare

  • Dagstuhl Seminar: "Algebraic Methods in Computational Complexity", 11.10.09 - 16.10.09, Seminar 09421, 2009.
  • Dagstuhl Seminar: "Computational Complexity of Discrete Problems", 20.03.11 - 25.03.11, Seminar 11121, 2011.

Publikationen

  • Hardness Results for Tournament Isomorphism and Automorphism
    Fabian Wagner,
    in proceedings: 32nd International Symposium, Mathematical Foundations of Computer Science (MFCS), LNCS 4708, pp. 572-583, 2007.
  • The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
    Thomas Thierauf, Fabian Wagner,
    technical report: ECCC, TR07-068, 2007.
    in proceedings: 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 633-644, 2008.
    in journal: Theory of Computing Systems, volume 47, no. 3, pp. 655-673, 2009.
  • Hardness Results for Isomorphism and Automorphism of Bounded Valence Graphs
    Fabian Wagner,
    in proceedings: 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Theory and Practice of Computer Science, Vol. 2 Student Research Forum, pp. 131-140, 2008.
  • Isomorphism and factorization - classical and quantum algorithms
    Sebastian Dörn, Daniel Haase, Jacobo Torán, Fabian Wagner,
    in book: Mathematical Analysis of Evolution, Information, and Complexity, editors: Wolfgang Arendt, Wolfgang P. Schleich, Wiley Verlag, 16:433-454, 2009
  • Planar Graph Isomorphism is in Log-Space
    Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner,
    earlier version: A Log-space Algorithm for Canonization of Planar Graphs, in arXiv:0809.2319v1, 2008.
    technical report: arXiv, 0809.2319v2, 2009.
    technical report: ECCC, TR09-052, 2009.
    in proceedings: 24th Annual IEEE Conference on Computational Complexity (CCC), pp. 203-214, 2009.
    in: Algebraic Methods in Computational Complexity, Dagstuhl Seminar Proceedings, no. 09421, 2010.
  • The complexity of planar graph isomorphism
    Jacobo Torán, Fabian Wagner,
    Bulletin of the European Association for Theoretical Computer Science (EATCS), 97:60-82, 2009. (www.eatcs.org/images/bulletin/beatcs97.pdf)
  • Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Log-Space
    Thomas Thierauf, Fabian Wagner,
    technical report: ECCC, TR09-029, 2009.
    in proceedings: 17th International Symposium, Fundamentals of Computation Theory (FCT), LNCS 5699, pp. 323-334, 2009.
  • Isomorphism for K3,3-free and K5-free Graphs is in Log-Space
    Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner,
    in proceedings: 29th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 145-156, 2009.
  • Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
    Bireswar Das, Jacobo Torán, Fabian Wagner,
    technical report: ECCC, TR09-094, 2009.
    in proceedings: 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 227-238, 2010.
    in journal: Information and Computation, 217, pp. 71-83, 2012.
  • On the Complexity of Isomorphism Testing for Restricted Classes of Graphs
    Fabian Wagner,
    Dissertation, Ph.D. thesis: VTS-ID/7264, 2010. (http://vts.uni-ulm.de/doc.asp?id=7264)
    Book: Isomorphism Testing for Restricted Graph Classes - On the complexity of isomorphism testing and reachability problems for restricted graph classes, Süddeutscher Verlag für Hochschulschriften, 2010.
  • Graph Isomorphism is not AC0 reducible to Group Isomorphism
    Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner,
    technical report: ECCC, TR10-117, 2010.
    In proceedings: 30th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 317-326, 2010.
  • Graphs of Bounded Treewidth can be Canonized in AC¹
    Fabian Wagner,
    technical report: ECCC, TR11-032, 2011.
    In proceedings: 6th International Computer Science Symposium in Russia, (CSR), LNCS 6651, pp. 209-222, 2011.
  • On the Complexity of Group Isomorphism
    Fabian Wagner,
    technical report: ECCC, Revision #4 to TR11-052, 2012.
    There is an updated and improved version of the results for p-groups in arXiv:1205.0642 and TR11-052 in ECCC, see arXiv:1312.1755.
  • Beating the Generator-Enumeration Bound for p-Group Isomorphism
    David J. Rosenbaum, Fabian Wagner
    technical report: arXiv:1312.1755, 2013.
    in journal: Theoretical Computer Science, dx.doi.org/10.1016/j.tcs.2015.05.036, vol. 593, pp. 16-25, 2015.
  • Counting the Number of Perfect Matchings in K5-free Graphs
    Simon Straub, Thomas Thierauf, Fabian Wagner
    technical report: ECCC TR14-079, 2014.
    IEEE Conference on Computational Complexity (CCC), pp. 66-77, 2014.