# Research Interests

- Graph isomorphism and canonization
- Space bounded algorithms
- Complexity and algorithms
- One-way functions and pseudo-random generators
- Cryptographic protocols

# Papers

*BibTeX*

@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.

*BibTeX*

@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.

*BibTeX*

@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.

*BibTeX*

@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)

*BibTeX*

@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)

*BibTeX*

@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).

*BibTeX*

@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).

*BibTeX*

@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.

*BibTeX*

@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.

*BibTeX*

@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)

*BibTeX*

@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).

*BibTeX*

@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