Johannes Köbler

136 papers A* 2A 12B 19C 4Misc 3Journal 78Unranked 16
YearRankTypeTitle / Venue / Authors
2025 J jnl
On a Hierarchy of Spectral Isomorphism Invariants.
Comput. Complex.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2025 J jnl
On the expressibility of the reconstructional color refinement.
Theor. Comput. Sci.
Vikraman Arvind, Johannes Köbler, Oleg Verbitsky
2024 J jnl
Gathering Information about a Graph by Counting Walks from a Single Vertex.
CoRR
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky, Maksim Zhukovskii
2024 A conf
On a Hierarchy of Spectral Invariants for Graphs.
STACS
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2024 J jnl
On the Expressibility of the Reconstructional Color Refinement.
CoRR
Vikraman Arvind, Johannes Köbler, Oleg Verbitsky
2023 J jnl
On a Hierarchy of Spectral Isomorphism Invariants.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2022 J jnl
On the Weisfeiler-Leman dimension of fractional packing.
Inf. Comput.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2022 J jnl
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs.
ACM Trans. Comput. Theory
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan
2021 J jnl
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.
SIAM J. Discret. Math.
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2021 J jnl
Local WL invariance and hidden shades of regularity.
Discret. Appl. Math.
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2021 J jnl
Parameterized Complexity of Small Weight Automorphisms and Isomorphisms.
Algorithmica
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2021 C conf
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties.
CIAC
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
2021 J jnl
The Weisfeiler-Leman algorithm and recognition of graph properties.
Theor. Comput. Sci.
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
2020 A conf
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.
STACS
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 J jnl
Local WL Invariance and Hidden Shades of Regularity.
CoRR
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 J jnl
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.
J. Comput. Syst. Sci.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 C conf
On the Weisfeiler-Leman Dimension of Fractional Packing.
LATA
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 J jnl
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties.
CoRR
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
2019 J jnl
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.
CoRR
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2019 B conf
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties.
FCT
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2019 J jnl
On the Weisfeiler-Leman Dimension of Fractional Packing.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2018 J jnl
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2017 J jnl
Circular-arc hypergraphs: Rigidity via connectedness.
Discret. Appl. Math.
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2017 B conf
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
IPEC
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2017 J jnl
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
CoRR
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2017 J jnl
Graph Isomorphism, Color Refinement, and Compactness.
Comput. Complex.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2017 A conf
Parameterized Complexity of Small Weight Automorphisms.
STACS
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2016 J jnl
On the isomorphism problem for Helly circular-arc graphs.
Inf. Comput.
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2016 J jnl
Parameterized Complexity of Small Weight Automorphisms.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2016 J jnl
Solving Linear Equations Parameterized by Hamming Weight.
Algorithmica
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2016 J jnl
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace.
J. Discrete Algorithms
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2016 B conf
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs.
MFCS
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan
2016 J jnl
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan
2015 J jnl
Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
Algorithmica
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
2015 J jnl
Graph Isomorphism, Color Refinement, and Compactness.
CoRR
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 J jnl
Graph Isomorphism, Color Refinement, and Compactness.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 J jnl
Interval graph representation with given interval and intersection lengths.
J. Discrete Algorithms
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
2015 J jnl
Lowness results: the next generation.
Bull. EATCS
Johannes Köbler, Jacobo Torán
2015 — conf
On Tinhofer's Linear Programming Approach to Isomorphism Testing.
MFCS (2)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 B conf
On the Power of Color Refinement.
FCT
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 J jnl
On the isomorphism problem for decision trees and decision lists.
Theor. Comput. Sci.
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev
2014 J jnl
On the Isomorphism Problem for Helly Circular-Arc Graphs.
CoRR
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2014 B conf
Solving Linear Equations Parameterized by Hamming Weight.
IPEC
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
2014 J jnl
Solving Linear Equations Parameterized by Hamming Weight.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán
2013 J jnl
Circular-arc hypergraphs: Rigidity via Connectedness.
CoRR
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2013 B conf
Helly Circular-Arc Graph Isomorphism Is in Logspace.
MFCS
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2013 J jnl
Helly Circular-Arc Graph Isomorphism is in Logspace.
Electron. Colloquium Comput. Complex.
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2013 B conf
On the Isomorphism Problem for Decision Trees and Decision Lists.
FCT
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev
2013 J jnl
The Parallel Complexity of Graph Canonization Under Abelian Group Action.
Algorithmica
Vikraman Arvind, Johannes Köbler
2012 B conf
Approximate Graph Isomorphism.
MFCS
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Yadu Vasudev
2012 J jnl
Approximate Graph Isomorphism.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev
2012 J jnl
Around and Beyond the Isomorphism Problem for Interval Graphs.
Bull. EATCS
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2012 B conf
Interval Graph Representation with Given Interval and Intersection Lengths.
ISAAC
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
2012 J jnl
Interval graph representation with given interval and intersection lengths.
Electron. Colloquium Comput. Complex.
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe
2012 J jnl
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
CoRR
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2012 — conf
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace.
FSTTCS
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2012 J jnl
The isomorphism problem for k-trees is complete for logspace.
Inf. Comput.
Vikraman Arvind, Bireswar Das, Johannes Köbler, Sebastian Kuhnert
2011 Misc conf
Canonizing Hypergraphs under Abelian Group Action.
COCOON
Vikraman Arvind, Johannes Köbler
2011 J jnl
Interval Graphs: Canonical Representations in Logspace.
SIAM J. Comput.
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
2011 J jnl
Proof systems that take advice.
Inf. Comput.
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2010 — conf
Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
FSTTCS
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
2010 — conf
Interval Graphs: Canonical Representation in Logspace.
ICALP (1)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
2010 J jnl
Interval Graphs: Canonical Representation in Logspace.
Electron. Colloquium Comput. Complex.
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
2009 J jnl
Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
2009 C conf
Nondeterministic Instance Complexity and Proof Systems with Advice.
LATA
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2009 J jnl
Nondeterministic functions and the existence of optimal proof systems.
Theor. Comput. Sci.
Olaf Beyersdorff, Johannes Köbler, Jochen Messner
2009 J jnl
Parameterized learnability of juntas.
Theor. Comput. Sci.
Vikraman Arvind, Johannes Köbler, Wolfgang Lindner
2009 J jnl
Proof Systems that Take Advice.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2009 B conf
The Isomorphism Problem for k-Trees Is Complete for Logspace.
MFCS
Johannes Köbler, Sebastian Kuhnert
2009 J jnl
The Isomorphism Problem for k-Trees is Complete for Logspace.
Electron. Colloquium Comput. Complex.
Johannes Köbler, Sebastian Kuhnert
2008 Misc conf
A Logspace Algorithm for Partial 2-Tree Canonization.
CSR
Vikraman Arvind, Bireswar Das, Johannes Köbler
2008 Misc conf
From Invariants to Canonization in Parallel.
CSR
Johannes Köbler, Oleg Verbitsky
2008 J jnl
Nondeterministic Instance Complexity and Proof Systems with Advice.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2007 J jnl
A general dimension for query learning.
J. Comput. Syst. Sci.
José L. Balcázar, Jorge Castro, David Guijarro, Johannes Köbler, Wolfgang Lindner
2007 B conf
Parameterized Learnability of
ALT
Vikraman Arvind, Johannes Köbler, Wolfgang Lindner
2007 B conf
The Space Complexity of
ISAAC
Vikraman Arvind, Bireswar Das, Johannes Köbler
2006 J jnl
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].
J. Comput. Syst. Sci.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
2006 J jnl
From Invariants to Canonization in Parallel
CoRR
Johannes Köbler, Oleg Verbitsky
2006 J jnl
Learning Boolean Functions under the Uniform.
Bull. EATCS
Johannes Köbler, Wolfgang Lindner
2006 C conf
On Graph Isomorphism for Restricted Graph Classes.
CiE
Johannes Köbler
2006 A conf
On Hypergraph and Graph Isomorphism with Bounded Color Classes.
STACS
Vikraman Arvind, Johannes Köbler
2006 J jnl
The complexity of learning concept classes with polynomial general dimension.
Theor. Comput. Sci.
Johannes Köbler, Wolfgang Lindner
2004 J jnl
Average-case intractability vs. worst-case intractability.
Inf. Comput.
Johannes Köbler, Rainer Schuler
2003 J jnl
Completeness results for graph isomorphism.
J. Comput. Syst. Sci.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
2003 J jnl
Optimal proof systems imply complete sets for promise classes.
Inf. Comput.
Johannes Köbler, Jochen Messner, Jacobo Torán
2002 B conf
A General Dimension for Approximately Learning Boolean Functions.
ALT
Johannes Köbler, Wolfgang Lindner
2002 J jnl
New Lowness Results for ZPPNP and Other Complexity Classes.
J. Comput. Syst. Sci.
Vikraman Arvind, Johannes Köbler
2002 A conf
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.
STACS
Johannes Köbler, Jacobo Torán
2002 B conf
The Complexity of Learning Concept Classes with Polynomial General Dimension.
ALT
Johannes Köbler, Wolfgang Lindner
2001 J jnl
On pseudorandomness and resource-bounded measure.
Theor. Comput. Sci.
Vikraman Arvind, Johannes Köbler
2000 A conf
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.
STACS
Vikraman Arvind, Johannes Köbler
2000 — conf
Is the Standard Proof System for SAT P-Optimal?
FSTTCS
Johannes Köbler, Jochen Messner
2000 A conf
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.
STACS
Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán
2000 — conf
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation.
FSTTCS
Johannes Köbler, Wolfgang Lindner
2000 J jnl
Oracles in S
Int. J. Found. Comput. Sci.
Johannes Köbler, Wolfgang Lindner
1999 J jnl
Graph Isomorphism is Low for ZPP
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Johannes Köbler
1999 J jnl
The Complexity of Generating Test Instances.
Chic. J. Theor. Comput. Sci.
Christoph Karg, Johannes Köbler, Rainer Schuler
1998 J jnl
Average-Case Intractability vs. Worst-Case Intractability
Electron. Colloquium Comput. Complex.
Johannes Köbler, Rainer Schuler
1998 B conf
Average-Case Intractability vs. Worst-Case Intractability.
MFCS
Johannes Köbler, Rainer Schuler
1998 A conf
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets.
CCC
Johannes Köbler, Jochen Messner
1998 J jnl
New Collapse Consequences of NP Having Small Circuits.
SIAM J. Comput.
Johannes Köbler, Osamu Watanabe
1998 A conf
On the Resource Bounded Measure of P/poly.
CCC
Johannes Köbler, Wolfgang Lindner
1997 — conf
High Sets for NP.
Advances in Algorithms, Languages, and Complexity
Johannes Köbler, Uwe Schöning
1997 — conf
On Resource-Bounded Measure and Pseudorandomness.
FSTTCS
Vikraman Arvind, Johannes Köbler
1997 B conf
Oracles in Sigma
ALT
Johannes Köbler, Wolfgang Lindner
1997 A conf
The Complexity of Generating Test Instances.
STACS
Christoph Karg, Johannes Köbler, Rainer Schuler
1996 J jnl
Monotonous and Randomized Reductions to Sparse Sets.
RAIRO Theor. Informatics Appl.
Vikraman Arvind, Johannes Köbler, Martin Mundhenk
1996 J jnl
On the Power of Generalized MOD-Classes.
Math. Syst. Theory
Johannes Köbler, Seinosuke Toda
1996 J jnl
Upper Bounds for the Complexity of Sparse and Tally Descriptions.
Math. Syst. Theory
Vikraman Arvind, Johannes Köbler, Martin Mundhenk
1995 J jnl
If NP has Polynomial-Size Circuits, then MA=AM.
Theor. Comput. Sci.
Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler
1995 A* conf
New Collapse Consequences of NP Having Small Circuits.
ICALP
Johannes Köbler, Osamu Watanabe
1995 J jnl
On Helping and Interactive Proof Systems.
Int. J. Found. Comput. Sci.
Vikraman Arvind, Johannes Köbler, Rainer Schuler
1995 J jnl
On Reductions to Sets that Avoid EXPSPACE.
Inf. Process. Lett.
Vikraman Arvind, Johannes Köbler, Martin Mundhenk
1995 — conf
On the Structure of Low Sets.
SCT
Johannes Köbler
1995 J jnl
The Power of the Middle Bit of a #P Function.
J. Comput. Syst. Sci.
Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán
1994 J jnl
Complexity-Restricted Advice Functions.
SIAM J. Comput.
Johannes Köbler, Thomas Thierauf
1994 J jnl
Locating P/poly Optimally in the Extended Low Hierarchy.
Theor. Comput. Sci.
Johannes Köbler
1994 B conf
On Helping and Interactive Proof Systems.
ISAAC
Vikraman Arvind, Johannes Köbler, Rainer Schuler
1993 B conf
Hausdorff Reductions to Sparse Sets and to Sets of High Information Content.
MFCS
Vikraman Arvind, Johannes Köbler, Martin Mundhenk
1993 A conf
Locating P/poly Optimally in the Extended Low Hierarchy.
STACS
Johannes Köbler
1993 — conf
On the Power of Generalized MOD-Classes.
SCT
Johannes Köbler, Seinosuke Toda
1993 — book
The Graph Isomorphism Problem: Its Structural Complexity
Johannes Köbler, Uwe Schöning, Jacobo Torán
1992 A conf
Graph Isomorphism is Low for PP.
STACS
Johannes Köbler, Uwe Schöning, Jacobo Torán
1992 J jnl
Graph Isomorphism is Low for PP.
Comput. Complex.
Johannes Köbler, Uwe Schöning, Jacobo Torán
1992 B conf
Lowness and the Complexity of Sparse and Tally Descriptions.
ISAAC
Vikraman Arvind, Johannes Köbler, Martin Mundhenk
1992 — conf
On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.
FSTTCS
Vikraman Arvind, Johannes Köbler, Martin Mundhenk
1992 — conf
Reductions to Sets of Low Information Content.
Complexity Theory: Current Research
Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf
1992 A* conf
Reductions to Sets of Low Information Content.
ICALP
Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf
1992 — conf
The Power of the Middle Bit.
SCT
Frederic Green, Johannes Köbler, Jacobo Torán
1992 J jnl
Turing Machines with Few Accepting Computations and Low Sets for PP.
J. Comput. Syst. Sci.
Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán
1990 — conf
Complexity Classes with Advice.
SCT
Johannes Köbler, Thomas Thierauf
1989 J jnl
On Counting and Approximation.
Acta Informatica
Johannes Köbler, Uwe Schöning, Jacobo Torán
1989 — —
Strukturelle Komplexität von Anzahlproblemen.
Johannes Köbler
1989 — conf
Turing Machines with few Accepting Computations and low Sets for PP.
SCT
Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán
1988 — conf
On Counting and Approximation.
CAAP
Johannes Köbler, Uwe Schöning, Jacobo Torán
1987 J jnl
The Difference and Truth-Table Hierarchies for NP.
RAIRO Theor. Informatics Appl.
Johannes Köbler, Uwe Schöning, Klaus W. Wagner