Forschungsinteressen
- Isomorphie und Kanonisierung von Graphen
- Platzbeschränkte Algorithmen
- Komplexität und Algorithmen
- Einwegfunktionen und Pseudozufallsgeneratoren
- Kryptographische Protokolle
Artikel
@InProceedings{AKKT17, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Jacobo Torán}, title = {Parameterized complexity of small weight automorphisms}, year = 2017, booktitle = {Proc. 34th STACS}, series = {LIPIcs}, number = 66, publisher = {Leibniz-Zentrum für Informatik}, address = {Dagstuhl}, isbn = {978-3-95977-028-6}, pages = {7:1-7:13}, doi = {10.4230/LIPIcs.STACS.2017.7}, }
Parameterized complexity of
small weight automorphisms.
With V. Arvind,
Johannes
Köbler, Jacobo Torán.
Proceedings of 34th STACS. LIPIcs 66, 2017.
@InProceedings{AFKKR16, author = {V. Arvind and Frank Fuhlbrück and Johannes Köbler and Sebastian Kuhnert and Gaurav Rattan}, title = {The parameterized complexity of fixing number and vertex individualization in graphs}, year = 2016, booktitle = {Mathematical Foundations of Computer Science (Proceedings of MFCS 2016)}, editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier}, series = {LIPIcs}, number = 58, publisher = {Leibniz-Zentrum für Informatik}, location = {Dagstuhl}, isbn = {978-3-95977-016-3}, pages = {13:1--13:14}, doi = {10.4230/LIPIcs.MFCS.2016.13}, }
The parameterized complexity of
fixing number and vertex individualization in
graphs.
With V. Arvind,
Frank
Fuhlbrück, Johannes
Köbler, Gaurav
Rattan.
Mathematical Foundations of Computer Science (Proceedings
of 41st MFCS). LIPIcs 58, 2016.
@Article{AKKT16linearequations, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Jacobo Tor\'an}, title = {Solving linear equations parameterized by {Hamming} weight}, journal = {Algorithmica}, year = 2016, volume = 75, number = 2, pages = {322-338}, issn = {0178-4617}, doi = {10.1007/s00453-015-0098-3}, }
Solving linear
equations parameterized by Hamming weight.
With V. Arvind,
Johannes
Köbler, Jacobo Torán.
Algorithmica 75:2 (Jun. 2016), pp. 322–338.
@Article{KKV16hca, author = {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky}, title = {On the isomorphism problem for {Helly} circular-arc graphs}, journal = {Information and Computation}, year = 2016, volume = 247, month = 4, pages = {266-277}, issn = {0890-5401}, doi = {10.1016/j.ic.2016.01.006}, }
On the isomorphism problem for
Helly circular-arc graphs.
With Johannes
Köbler, Oleg
Verbitsky.
Information and Computation 247:266–277 (2016)
@Article{KKV16pca, author = {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky}, title = {Solving the canonical representation and star system problems for proper circular-arc graphs in logspace}, journal = {Journal of Discrete Algorithms}, year = 2016, volume = {38-41}, pages = {38-49}, issn = {1570-8667}, doi = {10.1016/j.jda.2016.03.001}, }
Solving the canonical
representation and star system problems for proper circular-arc
graphs in logspace.
With Johannes
Köbler, Oleg
Verbitsky.
Journal of Discrete Algorithms 38–41:38–49 (2016)
@Article{KKW15intervalintersections, author = {Johannes Köbler and Sebastian Kuhnert and Osamu Watanabe}, title = {Interval graph representation with given interval and intersection lengths}, journal = {Journal of Discrete Algorithms}, year = 2015, volume = 34, month = 9, pages = {108-117}, issn = {1570-8667}, doi = {10.1016/j.jda.2015.05.011}, }
Interval graph
representation with given interval and intersection
lengths.
With Johannes
Köbler, Osamu
Watanabe.
Journal of Discrete Algorithms 34:108–117 (Sep. 2015).
@Article{AKKRV15dtdliso, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Gaurav Rattan and Yadu Vasudev}, title = {On the isomorphism problem for decision trees and decision lists}, journal = {Theoretical Computer Science}, year = 2015, volume = 590, month = 7, pages = {38-54}, issn = {0304-3975}, doi = {10.1016/j.tcs.2015.01.025}, }
On the isomorphism problem
for decision trees and decision lists.
With V. Arvind,
Johannes
Köbler, Gaurav
Rattan, Yadu
Vasudev.
Theoretical Computer Science 590:38–54 (2015).
@InProceedings{AKKV12approxgi, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Yadu Vasudev}, title = {Approximate Graph Isomorphism}, editor = {Branislav Rovan and Vladimiro Sassone and Peter Widmayer}, booktitle = {Mathematical Foundations of Computer Science (Proceedings of MFCS 2012)}, year = 2012, series = {LNCS}, number = 7464, publisher = {Springer}, address = {Berlin}, isbn = {978-3-642-32588-5}, doi = {10.1007/978-3-642-32589-2_12}, pages = {100-111}, }
Approximate Graph
Isomorphism.
With V. Arvind,
Johannes
Köbler, Yadu
Vasudev.
Mathematical Foundations of Computer Science (Proceedings
of 37th MFCS). Springer, 2012.
Pp. 100-111.
@Article{KKV12intervalgraphs, author = {Sebastian Kuhnert}, title = {Around and beyond the isomorphism problem for interval graphs}, journal = {Bulletin of the EATCS}, note = {Computational Complexity Column}, year = 2012, number = 107, url = {http://bulletin.eatcs.org/index.php/beatcs/article/view/68}, pages = {44-71}, }
Around and beyond the
isomorphism problem for interval graphs.
With Johannes
Köbler, Oleg
Verbitsky.
The Computational Complexity Column ed. by V. Arvind.
Bulletin
of the EATCS 107 (2012). Pp. 44-71.
@Article{ADKK12ktree-canonization, author = {V. Arvind and Bireswar Das and Johannes Köbler and Sebastian Kuhnert}, title = {The isomorphism problem for $k$-trees is complete for logspace}, journal = {Information and Computation}, year = 2012, volume = 217, month = 8, pages = {1-11}, issn = {0890-5401}, doi = {10.1016/j.ic.2012.04.002}, }
The isomorphism problem for
k-trees is complete for logspace.
With V. Arvind,
Bireswar
Das, Johannes
Köbler.
Information and Computation 217:1–11 (Aug. 2012)
@Article{KKLV11intervalgraphs, author = {Johannes Köbler and Sebastian Kuhnert and Bastian Laubner and Oleg Verbitsky}, title = {Interval graphs: Canonical representations in logspace}, journal = {SIAM Journal on Computing}, year = 2011, volume = 40, number = 5, pages = {1292-1315}, issn = {1501-1526}, doi = {10.1137/10080395X}, }
Interval graphs:
Canonical representations in logspace.
With Johannes
Köbler, Bastian
Laubner, Oleg
Verbitsky.
SIAM Journal on Computing 40(5):1292–1315 (2011).
@InProceedings{Kuh09edgefinding, author = {Sebastian Kuhnert}, title = {Efficient edge-finding on unary resources with optional activities}, editor = {Dietmar Seipel and Michael Hanus and Armin Wolf}, booktitle = {Applications of Declarative Programming and Knowledge Management (Proceedings of INAP/WLP 2007)}, year = 2009, series = {LNCS}, number = 5437, publisher = {Springer}, address = {Berlin}, isbn = {978-3-642-00674-6}, doi = {10.1007/978-3-642-00675-3_3}, pages = {38-53}, }
Efficient edge-finding on
unary resources with optional activities.
Applications of Declarative Programming and Knowledge
Management (Proceedings of
INAP/WLP 2007). Springer, 2009. Pp. 38-53.
Ausgewählte Vorträge
Interval graphs:
Canonical representations in logspace.
Talk at 37th ICALP, Bordeaux,
France.
Delivered on July 7th, 2010.
The Isomorphism problem for
k-trees is complete for logspace.
Talk at 34th MFCS, Novy
Smokovec, Slovakia.
Delivered on August 24th, 2009.
Satz von
Mahaney.
Referat im Rahmen der Veranstaltung Strukturelle
Komplexitätstheorie.
Gehalten am 7.12.2004.
Lehre
WiSe 2017/18
- Software Engineering (Übung)
WiSe 2016/17
SoSe 2016
- Kryptografie (Seminar Komplexität und Kryptologie)
WiSe 2015/16
- Parametrisierte Komplexität (Seminar Komplexität und Kryptologie)
SoSe 2015
- Graphalgorithmen (Vorlesung)
WiSe 2014/15
- Fortgeschrittene Algorithmen und Datenstrukturen (Seminar Komplexität und Kryptologie)
SoSe 2014
- Graphalgorithmen (Seminar Komplexität und Kryptologie)
WiSe 2013/14
- Einführung in die Theoretische Informatik (Übung)
- Fixed Parameter Tractability (Seminar Komplexität und Kryptologie)
SoSe 2013
- Komplexität und Kryptologie (Seminar)
WiSe 2012/13
- Graphisomorphie (Seminar Komplexität und Kryptologie)
SoSe 2012
- Hashfunktionen (Seminar Komplexität und Kryptologie)
WiSe 2011/12
- Probabilistically Checkable Proofs und Approximation (Seminar Komplexität und Kryptologie)
SoSe 2011
- Graphisomorphie (Seminar Komplexität und Kryptologie)
WiSe 2010/11
- Erzeugung und Verwendung von Zufall (Seminar Komplexität und Kryptologie)
SoSe 2010
- Theoretische Informatik 3 (Übung)
- Kryptologie 2 (Übung)
- Aktuelle Entwicklungen in der Kryptographie (Seminar)
WiSe 2009/10
- Theoretische Informatik 2 (Übung)
- Kryptologie 1 (Übung)
SoSe 2009
- Theoretische Informatik 3 (Übung)
- Interaktive Beweise (Seminar)
- Moderne Kryptoverfahren (Proseminar)
WiSe 2008/09
- Theoretische Informatik 2 (Übung)
- Komplexitätstheorie (Übung)
- Kryptographische Protokolle (Seminar Komplexität und Kryptographie)
SoSe 2008
- Theoretische Informatik 3 (Übung)
- Kryptologie 2 (Übung)
- Hürden zum Lösen des P-NP-Problems (Seminar Komplexität und Kryptologie)
WiSe 2007/08
- Kryptologie 1 (Übung)
- Pseudozufallsgeneratoren (Seminar Komplexität und Kryptographie)
WiSe 2005/06 bis SoSe 2007
Als Tutor habe ich an der TU Berlin folgende Veranstaltungen betreut:
- Theoretische Grundlagen der Informatik 2: Berechenbarkeit und Komplexität
- Theoretische Grundlagen der Informatik 3: Aussagen- und Prädikatenlogik
- Theoretische Grundlagen der Informatik 2: Signaturen, Algebren und Spezifikationen
- Mathematik für Informatiker 1: Axiomatik, Induktion, Konvergenz, Analysis