Johannes Köbler

ORCID

Publication Activity (10 Years)

Years Active: 1987-2024
Publications (10 Years): 30

Top Venues

CoRR

Algorithmica

Electron. Colloquium Comput. Complex.

STACS

University of Stuttgart, Germany (PHD)

Education History

University of Stuttgart, Germany

PHD

Publications

Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On a Hierarchy of Spectral Invariants for Graphs. STACS (2024)
Vikraman Arvind, Johannes Köbler, Oleg Verbitsky
On the Expressibility of the Reconstructional Color Refinement. CoRR (2024)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On a Hierarchy of Spectral Isomorphism Invariants. CoRR (2023)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On the Weisfeiler-Leman dimension of fractional packing. Inf. Comput. 288 (2022)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. ACM Trans. Comput. Theory 14 (2) (2022)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. SIAM J. Discret. Math. 35 (3) (2021)
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CIAC (2021)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Parameterized Complexity of Small Weight Automorphisms and Isomorphisms. Algorithmica 83 (12) (2021)
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
The Weisfeiler-Leman algorithm and recognition of graph properties. Theor. Comput. Sci. 895 (2021)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Local WL invariance and hidden shades of regularity. Discret. Appl. Math. 305 (2021)
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CoRR (2020)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. STACS (2020)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On the Weisfeiler-Leman Dimension of Fractional Packing. LATA (2020)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Local WL Invariance and Hidden Shades of Regularity. CoRR (2020)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci. 113 (2020)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. FCT (2019)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On the Weisfeiler-Leman Dimension of Fractional Packing. CoRR (2019)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. CoRR (2019)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. CoRR (2018)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
Graph Isomorphism, Color Refinement, and Compactness. Comput. Complex. 26 (3) (2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. IPEC (2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. CoRR (2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Parameterized Complexity of Small Weight Automorphisms. STACS (2017)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Circular-arc hypergraphs: Rigidity via connectedness. Discret. Appl. Math. 217 (2017)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace. J. Discrete Algorithms (2016)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Parameterized Complexity of Small Weight Automorphisms. Electron. Colloquium Comput. Complex. 23 (2016)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
On the isomorphism problem for Helly circular-arc graphs. Inf. Comput. 247 (2016)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. MFCS (2016)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Solving Linear Equations Parameterized by Hamming Weight. Algorithmica 75 (2) (2016)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. CoRR (2016)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
Graph Isomorphism, Color Refinement, and Compactness. Electron. Colloquium Comput. Complex. 22 (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
Graph Isomorphism, Color Refinement, and Compactness. CoRR (2015)
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
Interval graph representation with given interval and intersection lengths. J. Discrete Algorithms 34 (2015)
Johannes Köbler, Jacobo Torán
Lowness results: the next generation. Bull. EATCS 117 (2015)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev
On the isomorphism problem for decision trees and decision lists. Theor. Comput. Sci. 590 (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
On the Power of Color Refinement. FCT (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
On Tinhofer's Linear Programming Approach to Isomorphism Testing. MFCS (2) (2015)
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. Algorithmica 71 (1) (2015)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
On the Isomorphism Problem for Helly Circular-Arc Graphs. CoRR (2014)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
Solving Linear Equations Parameterized by Hamming Weight. IPEC (2014)
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán
Solving Linear Equations Parameterized by Hamming Weight. Electron. Colloquium Comput. Complex. 21 (2014)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Circular-arc hypergraphs: Rigidity via Connectedness. CoRR (2013)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Helly Circular-Arc Graph Isomorphism Is in Logspace. MFCS (2013)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev
On the Isomorphism Problem for Decision Trees and Decision Lists. FCT (2013)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Helly Circular-Arc Graph Isomorphism is in Logspace. Electron. Colloquium Comput. Complex. 20 (2013)
Vikraman Arvind, Johannes Köbler
The Parallel Complexity of Graph Canonization Under Abelian Group Action. Algorithmica 67 (2) (2013)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Yadu Vasudev
Approximate Graph Isomorphism. MFCS (2012)
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev
Approximate Graph Isomorphism. Electron. Colloquium Comput. Complex. 19 (2012)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace. FSTTCS (2012)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space CoRR (2012)
Vikraman Arvind, Bireswar Das, Johannes Köbler, Sebastian Kuhnert
The isomorphism problem for k-trees is complete for logspace. Inf. Comput. 217 (2012)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Around and Beyond the Isomorphism Problem for Interval Graphs. Bull. EATCS 107 (2012)
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe
Interval graph representation with given interval and intersection lengths. Electron. Colloquium Comput. Complex. 19 (2012)
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
Interval Graph Representation with Given Interval and Intersection Lengths. ISAAC (2012)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Interval Graphs: Canonical Representations in Logspace. SIAM J. Comput. 40 (5) (2011)
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Proof systems that take advice. Inf. Comput. 209 (3) (2011)
Vikraman Arvind, Johannes Köbler
Canonizing Hypergraphs under Abelian Group Action. COCOON (2011)
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. FSTTCS (2010)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Interval Graphs: Canonical Representation in Logspace. Electron. Colloquium Comput. Complex. 17 (2010)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Interval Graphs: Canonical Representation in Logspace. ICALP (1) (2010)
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. Electron. Colloquium Comput. Complex. 16 (2009)
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Nondeterministic Instance Complexity and Proof Systems with Advice. LATA (2009)
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Proof Systems that Take Advice. Electron. Colloquium Comput. Complex. 16 (2009)
Olaf Beyersdorff, Johannes Köbler, Jochen Messner
Nondeterministic functions and the existence of optimal proof systems. Theor. Comput. Sci. 410 (38-40) (2009)
Johannes Köbler, Sebastian Kuhnert
The Isomorphism Problem for k-Trees Is Complete for Logspace. MFCS (2009)
Vikraman Arvind, Johannes Köbler, Wolfgang Lindner
Parameterized learnability of juntas. Theor. Comput. Sci. 410 (47-49) (2009)
Johannes Köbler, Sebastian Kuhnert
The Isomorphism Problem for k-Trees is Complete for Logspace. Electron. Colloquium Comput. Complex. 16 (2009)
Johannes Köbler, Oleg Verbitsky
From Invariants to Canonization in Parallel. CSR (2008)
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Nondeterministic Instance Complexity and Proof Systems with Advice. Electron. Colloquium Comput. Complex. 15 (075) (2008)
Vikraman Arvind, Bireswar Das, Johannes Köbler
A Logspace Algorithm for Partial 2-Tree Canonization. CSR (2008)
José L. Balcázar, Jorge Castro, David Guijarro, Johannes Köbler, Wolfgang Lindner
A general dimension for query learning. J. Comput. Syst. Sci. 73 (6) (2007)
Vikraman Arvind, Johannes Köbler, Wolfgang Lindner
-Juntas and Related Problems. ALT (2007)
Vikraman Arvind, Bireswar Das, Johannes Köbler
-Tree Isomorphism. ISAAC (2007)
Vikraman Arvind, Johannes Köbler
On Hypergraph and Graph Isomorphism with Bounded Color Classes. STACS (2006)
Johannes Köbler, Wolfgang Lindner
Learning Boolean Functions under the Uniform. Bull. EATCS 89 (2006)
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566]. J. Comput. Syst. Sci. 72 (4) (2006)
Johannes Köbler, Oleg Verbitsky
From Invariants to Canonization in Parallel CoRR (2006)
Johannes Köbler, Wolfgang Lindner
The complexity of learning concept classes with polynomial general dimension. Theor. Comput. Sci. 350 (1) (2006)
Johannes Köbler
On Graph Isomorphism for Restricted Graph Classes. CiE (2006)
Johannes Köbler, Rainer Schuler
Average-case intractability vs. worst-case intractability. Inf. Comput. 190 (1) (2004)
Johannes Köbler, Jochen Messner, Jacobo Torán
Optimal proof systems imply complete sets for promise classes. Inf. Comput. 184 (1) (2003)
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66 (3) (2003)
Johannes Köbler, Wolfgang Lindner
The Complexity of Learning Concept Classes with Polynomial General Dimension. ALT (2002)
Johannes Köbler, Jacobo Torán
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3. STACS (2002)
Johannes Köbler, Wolfgang Lindner
A General Dimension for Approximately Learning Boolean Functions. ALT (2002)
Vikraman Arvind, Johannes Köbler
New Lowness Results for ZPPNP and Other Complexity Classes. J. Comput. Syst. Sci. 65 (2) (2002)
Vikraman Arvind, Johannes Köbler
On pseudorandomness and resource-bounded measure. Theor. Comput. Sci. 255 (1-2) (2001)
Johannes Köbler, Wolfgang Lindner
are Sufficient for Exact Learning. Int. J. Found. Comput. Sci. 11 (4) (2000)
Johannes Köbler, Jochen Messner
Is the Standard Proof System for SAT P-Optimal? FSTTCS (2000)
Johannes Köbler, Wolfgang Lindner
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation. FSTTCS (2000)
Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. STACS (2000)
Vikraman Arvind, Johannes Köbler
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. STACS (2000)
Christoph Karg, Johannes Köbler, Rainer Schuler
The Complexity of Generating Test Instances. Chic. J. Theor. Comput. Sci. 1999 (1999)
Vikraman Arvind, Johannes Köbler
and other Lowness results. Electron. Colloquium Comput. Complex. 6 (33) (1999)
Johannes Köbler, Rainer Schuler
Average-Case Intractability vs. Worst-Case Intractability. MFCS (1998)
Johannes Köbler, Rainer Schuler
Average-Case Intractability vs. Worst-Case Intractability Electron. Colloquium Comput. Complex. 5 (37) (1998)
Johannes Köbler, Wolfgang Lindner
On the Resource Bounded Measure of P/poly. Computational Complexity Conference (1998)
Johannes Köbler, Jochen Messner
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. Computational Complexity Conference (1998)
Johannes Köbler, Osamu Watanabe
New Collapse Consequences of NP Having Small Circuits. SIAM J. Comput. 28 (1) (1998)
Johannes Köbler, Uwe Schöning
High Sets for NP. Advances in Algorithms, Languages, and Complexity (1997)

Johannes Köbler.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Johannes Köbler