| 2024 | STACS | On a Hierarchy of Spectral Invariants for Graphs. | Vikraman Arvind, Frank Fuhlbrck, Johannes Kbler, Oleg Verbitsky |
| 2021 | CIAC | The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. | Frank Fuhlbrck, Johannes Kbler, Ilia Ponomarenko, Oleg Verbitsky |
| 2020 | LATA | On the Weisfeiler-Leman Dimension of Fractional Packing. | Vikraman Arvind, Frank Fuhlbrck, Johannes Kbler, Oleg Verbitsky |
| 2020 | STACS | Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. | Frank Fuhlbrck, Johannes Kbler, Oleg Verbitsky |
| 2019 | FCT | On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. | Vikraman Arvind, Frank Fuhlbrck, Johannes Kbler, Oleg Verbitsky |
| 2017 | STACS | Parameterized Complexity of Small Weight Automorphisms. | Vikraman Arvind, Johannes Kbler, Sebastian Kuhnert, Jacobo Torn |
| 2016 | MFCS | The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. | Vikraman Arvind, Frank Fuhlbrck, Johannes Kbler, Sebastian Kuhnert, Gaurav Rattan |
| 2015 | FCT | On the Power of Color Refinement. | Vikraman Arvind, Johannes Kbler, Gaurav Rattan, Oleg Verbitsky |
| 2015 | MFCS | On Tinhofer's Linear Programming Approach to Isomorphism Testing. | Vikraman Arvind, Johannes Kbler, Gaurav Rattan, Oleg Verbitsky |
| 2013 | FCT | On the Isomorphism Problem for Decision Trees and Decision Lists. | Vikraman Arvind, Johannes Kbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev |
| 2013 | MFCS | Helly Circular-Arc Graph Isomorphism Is in Logspace. | Johannes Kbler, Sebastian Kuhnert, Oleg Verbitsky |
| 2012 | ISAAC | Interval Graph Representation with Given Interval and Intersection Lengths. | Johannes Kbler, Sebastian Kuhnert, Osamu Watanabe |
| 2012 | MFCS | Approximate Graph Isomorphism. | Vikraman Arvind, Johannes Kbler, Sebastian Kuhnert, Yadu Vasudev |
| 2011 | COCOON | Canonizing Hypergraphs under Abelian Group Action. | Vikraman Arvind, Johannes Kbler |
| 2010 | ICALP | Interval Graphs: Canonical Representation in Logspace. | Johannes Kbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky |
| 2009 | LATA | Nondeterministic Instance Complexity and Proof Systems with Advice. | Olaf Beyersdorff, Johannes Kbler, Sebastian Mller |
| 2009 | MFCS | The Isomorphism Problem for k-Trees Is Complete for Logspace. | Johannes Kbler, Sebastian Kuhnert |
| 2008 | CSR | A Logspace Algorithm for Partial 2-Tree Canonization. | Vikraman Arvind, Bireswar Das, Johannes Kbler |
| 2008 | CSR | From Invariants to Canonization in Parallel. | Johannes Kbler, Oleg Verbitsky |
| 2007 | ALT | Parameterized Learnability of | Vikraman Arvind, Johannes Kbler, Wolfgang Lindner |
| 2007 | ISAAC | The Space Complexity of | Vikraman Arvind, Bireswar Das, Johannes Kbler |
| 2006 | CiE | On Graph Isomorphism for Restricted Graph Classes. | Johannes Kbler |
| 2006 | STACS | On Hypergraph and Graph Isomorphism with Bounded Color Classes. | Vikraman Arvind, Johannes Kbler |
| 2002 | ALT | A General Dimension for Approximately Learning Boolean Functions. | Johannes Kbler, Wolfgang Lindner |
| 2002 | ALT | The Complexity of Learning Concept Classes with Polynomial General Dimension. | Johannes Kbler, Wolfgang Lindner |
| 2002 | STACS | The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3. | Johannes Kbler, Jacobo Torn |
| 2000 | STACS | Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. | Vikraman Arvind, Johannes Kbler |
| 2000 | STACS | Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk, Jacobo Torn |
| 1998 | MFCS | Average-Case Intractability vs. Worst-Case Intractability. | Johannes Kbler, Rainer Schuler |
| 1997 | ALT | Oracles in Sigma | Johannes Kbler, Wolfgang Lindner |
| 1997 | STACS | The Complexity of Generating Test Instances. | Christoph Karg, Johannes Kbler, Rainer Schuler |
| 1995 | ICALP | New Collapse Consequences of NP Having Small Circuits. | Johannes Kbler, Osamu Watanabe |
| 1994 | ISAAC | On Helping and Interactive Proof Systems. | Vikraman Arvind, Johannes Kbler, Rainer Schuler |
| 1993 | MFCS | Hausdorff Reductions to Sparse Sets and to Sets of High Information Content. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk |
| 1993 | STACS | Locating P/poly Optimally in the Extended Low Hierarchy. | Johannes Kbler |
| 1992 | ICALP | Reductions to Sets of Low Information Content. | Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Kbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schning, Riccardo Silvestri, Thomas Thierauf |
| 1992 | ISAAC | Lowness and the Complexity of Sparse and Tally Descriptions. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk |
| 1992 | STACS | Graph Isomorphism is Low for PP. | Johannes Kbler, Uwe Schning, Jacobo Torn |