Johannes Köbler

Theor. Comput. Sci., 2025

2024

Gathering Information about a Graph by Counting Walks from a Single Vertex.

[BibT_eX]

[DOI]

CoRR, 2024

On a Hierarchy of Spectral Invariants for Graphs.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

On a Hierarchy of Spectral Isomorphism Invariants.

[BibT_eX]

[DOI]

CoRR, 2023

2021

Local WL invariance and hidden shades of regularity.

[BibT_eX]

[DOI]

Frank Fuhlbrück

Discret. Appl. Math., 2021

Parameterized Complexity of Small Weight Automorphisms and Isomorphisms.

[BibT_eX]

[DOI]

Algorithmica, 2021

The Weisfeiler-Leman Algorithm and Recognition of Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 12th International Conference, 2021

2020

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.

[BibT_eX]

[DOI]

Frank Fuhlbrück

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

On the Weisfeiler-Leman Dimension of Fractional Packing.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2020

2019

On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

2017

Circular-arc hypergraphs: Rigidity via connectedness.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Graph Isomorphism, Color Refinement, and Compactness.

[BibT_eX]

[DOI]

Comput. Complex., 2017

Parameterized Complexity of Small Weight Automorphisms.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

2016

On the isomorphism problem for Helly circular-arc graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2016

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Lowness results: the next generation.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

On Tinhofer's Linear Programming Approach to Isomorphism Testing.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

On the Power of Color Refinement.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

2014

Solving Linear Equations Parameterized by Hamming Weight.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013

The Parallel Complexity of Graph Canonization Under Abelian Group Action.

[BibT_eX]

[DOI]

Algorithmica, 2013

Helly Circular-Arc Graph Isomorphism Is in Logspace.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

On the Isomorphism Problem for Decision Trees and Decision Lists.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

2012

The isomorphism problem for k-trees is complete for logspace.

[BibT_eX]

[DOI]

Inf. Comput., 2012

Around and Beyond the Isomorphism Problem for Interval Graphs.

[BibT_eX]

[DOI]

Bull. EATCS, 2012

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space

[BibT_eX]

[DOI]

CoRR, 2012

Approximate Graph Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Interval Graph Representation with Given Interval and Intersection Lengths.

[BibT_eX]

[DOI]

Osamu Watanabe

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Interval Graphs: Canonical Representations in Logspace.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Canonizing Hypergraphs under Abelian Group Action.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

Interval Graphs: Canonical Representation in Logspace.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Colored Hypergraph Isomorphism is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Nondeterministic functions and the existence of optimal proof systems.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Theor. Comput. Sci., 2009

Parameterized learnability of juntas.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Proof Systems that Take Advice.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Sebastian Müller

Electron. Colloquium Comput. Complex., 2009

The Isomorphism Problem for k-Trees Is Complete for Logspace.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Nondeterministic Instance Complexity and Proof Systems with Advice.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Sebastian Müller

Proceedings of the Language and Automata Theory and Applications, 2009

2008

From Invariants to Canonization in Parallel.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2008

A Logspace Algorithm for Partial 2-Tree Canonization.

[BibT_eX]

[DOI]

Bireswar Das

Proceedings of the Computer Science, 2008

2007

A general dimension for query learning.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

The Space Complexity of k -Tree Isomorphism.

[BibT_eX]

[DOI]

Bireswar Das

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Parameterized Learnability of k -Juntas and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006

Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Learning Boolean Functions under the Uniform.

[BibT_eX]

Bull. EATCS, 2006

On Hypergraph and Graph Isomorphism with Bounded Color Classes.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

On Graph Isomorphism for Restricted Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the Logical Approaches to Computational Barriers, 2006

2003

Completeness results for graph isomorphism.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Optimal proof systems imply complete sets for promise classes.

[BibT_eX]

[DOI]

Inf. Comput., 2003

2002

New Lowness Results for ZPPNP and Other Complexity Classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.

[BibT_eX]

[DOI]

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

The Complexity of Learning Concept Classes with Polynomial General Dimension.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

A General Dimension for Approximately Learning Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001

On pseudorandomness and resource-bounded measure.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

2000

Oracles in Sp2 are Sufficient for Exact Learning.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2000

Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Is the Standard Proof System for SAT P-Optimal?

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999

Graph Isomorphism is Low for ZPPNP and other Lowness results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

1998

Average-Case Intractability vs. Worst-Case Intractability.

[BibT_eX]

[DOI]

Rainer Schuler

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

On the Resource Bounded Measure of P/poly.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

The Complexity of Generating Test Instances.

[BibT_eX]

[DOI]

Christoph Karg

Rainer Schuler

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

On Resource-Bounded Measure and Pseudorandomness.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1997

High Sets for NP.

[BibT_eX]

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

Oracles in Sigmap2 are Sufficient for Exact Learning.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996

Upper Bounds for the Complexity of Sparse and Tally Descriptions.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1996

Monotonous and Randomized Reductions to Sparse Sets.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1996

1995

If NP has Polynomial-Size Circuits, then MA=AM.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

The Power of the Middle Bit of a #P Function.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

On Reductions to Sets that Avoid EXPSPACE.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

New Collapse Consequences of NP Having Small Circuits.

[BibT_eX]

[DOI]

Osamu Watanabe

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

On the Structure of Low Sets.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Complexity-Restricted Advice Functions.

[BibT_eX]

[DOI]

Thomas Thierauf

SIAM J. Comput., 1994

On Helping and Interactive Proof Systems.

[BibT_eX]

[DOI]

Rainer Schuler

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993

Locating P/poly Optimally in the Extended Low Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

Hausdorff Reductions to Sparse Sets and to Sets of High Information Content.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

On the Power of Generalized MOD-Classes.

[BibT_eX]

[DOI]

Seinosuke Toda

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

The Graph Isomorphism Problem: Its Structural Complexity

[BibT_eX]

[DOI]

Progress in Theoretical Computer Science, Birkhäuser/Springer, ISBN: 978-1-4612-0333-9, 1993

1992

Graph Isomorphism is Low for PP.

[BibT_eX]

[DOI]

Proceedings of the STACS 92, 1992

Lowness and the Complexity of Sparse and Tally Descriptions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

Reductions to Sets of Low Information Content.

[BibT_eX]

Proceedings of the Complexity Theory: Current Research, 1992

The Power of the Middle Bit.

[BibT_eX]

[DOI]

Frederic Green

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1990

Complexity Classes with Advice.

[BibT_eX]

[DOI]

Thomas Thierauf

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Turing Machines with few Accepting Computations and low Sets for PP.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

Strukturelle Komplexität von Anzahlproblemen.

[BibT_eX]

[DOI]

PhD thesis, 1989

1988

On Counting and Approximation.

[BibT_eX]

[DOI]

Proceedings of the CAAP '88, 1988

1987

The Difference and Truth-Table Hierarchies for NP.

[BibT_eX]

[DOI]