Research Interests
- Graph isomorphism and canonization
- Space bounded algorithms
- Complexity and algorithms
- One-way functions and pseudo-random generators
- Cryptographic protocols
Papers
@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.
Selected talks
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.
Teaching
Winter term 2017/18
- Software Engineering (Tutorial)
Winter term 2016/17
- Introduction to Theoretical Computer Science (Tutorial)
Summer term 2016
- Cryptography (Seminar)
Winter term 2015/16
- Parameterized complexity (Seminar)
Summer term 2015
- Graph algorithms (Lecture)
Winter term 2014/15
- Advanced algorithms and data structures (Seminar)
Summer term 2014
- Graph algorithms (Seminar)
Winter term 2013/14
- Introduction to Theoretical Computer Science (Tutorial)
- Fixed Parameter Tractability (Seminar)
Summer term 2013
- Complexity and cryptology (Seminar)
Winter term 2012/13
- Graph isomorphism (Seminar)
Summer term 2012
- Hash functions (Seminar)
Winter term 2011/12
Summer term 2011
- Graph isomorphism (Seminar)
Winter term 2010/11
- Creating and using randomness (Seminar)
Summer term 2010
- Theoretical computer science 3 (Tutorial)
- Cryptology 2 (Tutorial)
- Recent developments in cryptography (Seminar)
Winter term 2009/10
- Theoretical computer science 2 (Tutorial)
- Cryptology 1 (Tutorial)
Summer term 2009
- Theoretical computer science 3 (Tutorial)
- Interactive Proofs (Seminar)
- Modern cryptography (Seminar)
Winter term 2008/09
- Theoretical computer science 2 (Tutorial)
- Complexity theory (Tutorial)
- Cryptographic protocols (Seminar)
Summer term 2008
- Theoretical computer science 3 (Tutorial)
- Cryptology 2 (Tutorial)
- Barriers for solving the P-NP-problem (Seminar)
Winter term 2007/08
- Cryptology 1 (Tutorial)
- Pseudo-random generators (Seminar)
Winter term 2005/6 to summer term 2007
I supported the following courses as a teaching assistant at TU Berlin:
- Theoretical foundations of computer science 2: Computability and complexity
- Theoretical foundations of computer science 3: Propositional and first order logic
- Theoretical foundations of computer science 2: Signatures, algebras, specifications
- Mathematics for computer scientists 1: Axioms of analysis, induction, convergence, calculus