Johannes Köbler

SIAM J. Discret. Math., 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

2020

On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

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

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

Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2016

On the isomorphism problem for Helly circular-arc graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2016

Parameterized Complexity of Small Weight Automorphisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Solving Linear Equations Parameterized by Hamming Weight.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

On the isomorphism problem for decision trees and decision lists.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Lowness results: the next generation.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

Colored Hypergraph Isomorphism is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

Algorithmica, 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

2013

Helly Circular-Arc Graph Isomorphism is in Logspace.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

The Parallel Complexity of Graph Canonization Under Abelian Group Action.

[BibT_eX]

[DOI]

Algorithmica, 2013

2012

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

[BibT_eX]

[DOI]

Inf. Comput., 2012

Interval graph representation with given interval and intersection lengths.

[BibT_eX]

[DOI]

Osamu Watanabe

Electron. Colloquium Comput. Complex., 2012

Approximate Graph Isomorphism.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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]

Electron. Colloquium Comput. Complex., 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

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Proof Systems that Take Advice.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Sebastian Müller

Electron. Colloquium Comput. Complex., 2009

2008

Nondeterministic Instance Complexity and Proof Systems with Advice.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Sebastian Müller

Electron. Colloquium Comput. Complex., 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

The complexity of learning concept classes with polynomial general dimension.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

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

The Complexity of Generating Test Instances.

[BibT_eX]

[DOI]

Christoph Karg

Rainer Schuler

Chic. J. Theor. Comput. Sci., 1999

1998

New Collapse Consequences of NP Having Small Circuits.

[BibT_eX]

[DOI]

Osamu Watanabe

SIAM J. Comput., 1998

Average-Case Intractability vs. Worst-Case Intractability

[BibT_eX]

[DOI]

Rainer Schuler

Electron. Colloquium Comput. Complex., 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

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

On the Power of Generalized MOD-Classes.

[BibT_eX]

[DOI]

Seinosuke Toda

Math. Syst. Theory, 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

On Helping and Interactive Proof Systems.

[BibT_eX]

[DOI]

Rainer Schuler

Int. J. Found. Comput. Sci., 1995

On the Structure of Low Sets.

[BibT_eX]

[DOI]

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

1994

Locating P/poly Optimally in the Extended Low Hierarchy.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Complexity-Restricted Advice Functions.

[BibT_eX]

[DOI]

Thomas Thierauf

SIAM J. Comput., 1994

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

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

Turing Machines with Few Accepting Computations and Low Sets for PP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Graph Isomorphism is Low for PP.

[BibT_eX]

[DOI]

Comput. Complex., 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

On Counting and Approximation.

[BibT_eX]

[DOI]

Acta Informatica, 1989

Strukturelle Komplexität von Anzahlproblemen.

[BibT_eX]

[DOI]

PhD thesis, 1989

1987

The Difference and Truth-Table Hierarchies for NP.

[BibT_eX]

[DOI]