Johannes Köbler

According to our database1, Johannes Köbler
  • authored at least 112 papers between 1987 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2017
Circular-arc hypergraphs: Rigidity via connectedness.
Discrete Applied Mathematics, 2017

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

Graph Isomorphism, Color Refinement, and Compactness.
Computational Complexity, 2017

Parameterized Complexity of Small Weight Automorphisms.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace.
J. Discrete Algorithms, 2016

On the isomorphism problem for Helly circular-arc graphs.
Inf. Comput., 2016

Parameterized Complexity of Small Weight Automorphisms.
Electronic Colloquium on Computational Complexity (ECCC), 2016

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

Solving Linear Equations Parameterized by Hamming Weight.
Algorithmica, 2016

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
On the isomorphism problem for decision trees and decision lists.
Theor. Comput. Sci., 2015

Interval graph representation with given interval and intersection lengths.
J. Discrete Algorithms, 2015

Graph Isomorphism, Color Refinement, and Compactness.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Lowness results: the next generation.
Bulletin of the EATCS, 2015

Graph Isomorphism, Color Refinement, and Compactness.
CoRR, 2015

Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
Algorithmica, 2015

On Tinhofer's Linear Programming Approach to Isomorphism Testing.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

On the Power of Color Refinement.
Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

2014
Solving Linear Equations Parameterized by Hamming Weight.
Electronic Colloquium on Computational Complexity (ECCC), 2014

On the Isomorphism Problem for Helly Circular-Arc Graphs.
CoRR, 2014

Solving Linear Equations Parameterized by Hamming Weight.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013
Helly Circular-Arc Graph Isomorphism is in Logspace.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Circular-arc hypergraphs: Rigidity via Connectedness.
CoRR, 2013

The Parallel Complexity of Graph Canonization Under Abelian Group Action.
Algorithmica, 2013

Helly Circular-Arc Graph Isomorphism Is in Logspace.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

On the Isomorphism Problem for Decision Trees and Decision Lists.
Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

2012
The isomorphism problem for k-trees is complete for logspace.
Inf. Comput., 2012

Interval graph representation with given interval and intersection lengths.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Approximate Graph Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Around and Beyond the Isomorphism Problem for Interval Graphs.
Bulletin of the EATCS, 2012

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

Approximate Graph Isomorphism.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Interval Graph Representation with Given Interval and Intersection Lengths.
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.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011
Interval Graphs: Canonical Representations in Logspace.
SIAM J. Comput., 2011

Proof systems that take advice.
Inf. Comput., 2011

Canonizing Hypergraphs under Abelian Group Action.
Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010
Interval Graphs: Canonical Representation in Logspace.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Interval Graphs: Canonical Representation in Logspace.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
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.
Theor. Comput. Sci., 2009

Parameterized learnability of juntas.
Theor. Comput. Sci., 2009

The Isomorphism Problem for k-Trees is Complete for Logspace.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Proof Systems that Take Advice.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Colored Hypergraph Isomorphism is Fixed Parameter Tractable.
Electronic Colloquium on Computational Complexity (ECCC), 2009

The Isomorphism Problem for k-Trees Is Complete for Logspace.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Nondeterministic Instance Complexity and Proof Systems with Advice.
Proceedings of the Language and Automata Theory and Applications, 2009

2008
Nondeterministic Instance Complexity and Proof Systems with Advice.
Electronic Colloquium on Computational Complexity (ECCC), 2008

From Invariants to Canonization in Parallel.
Proceedings of the Computer Science, 2008

A Logspace Algorithm for Partial 2-Tree Canonization.
Proceedings of the Computer Science, 2008

2007
A general dimension for query learning.
J. Comput. Syst. Sci., 2007

The Space Complexity of k -Tree Isomorphism.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Parameterized Learnability of k -Juntas and Related Problems.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006
The complexity of learning concept classes with polynomial general dimension.
Theor. Comput. Sci., 2006

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

Learning Boolean Functions under the Uniform.
Bulletin of the EATCS, 2006

From Invariants to Canonization in Parallel
CoRR, 2006

On Hypergraph and Graph Isomorphism with Bounded Color Classes.
Proceedings of the STACS 2006, 2006

On Graph Isomorphism for Restricted Graph Classes.
Proceedings of the Logical Approaches to Computational Barriers, 2006

2004
Average-case intractability vs. worst-case intractability.
Inf. Comput., 2004

2003
Completeness results for graph isomorphism.
J. Comput. Syst. Sci., 2003

Optimal proof systems imply complete sets for promise classes.
Inf. Comput., 2003

2002
New Lowness Results for ZPPNP and Other Complexity Classes.
J. Comput. Syst. Sci., 2002

The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.
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.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

A General Dimension for Approximately Learning Boolean Functions.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001
On pseudorandomness and resource-bounded measure.
Theor. Comput. Sci., 2001

2000
Oracles in Sp2 are Sufficient for Exact Learning.
Int. J. Found. Comput. Sci., 2000

Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.
Proceedings of the STACS 2000, 2000

Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.
Proceedings of the STACS 2000, 2000

Is the Standard Proof System for SAT P-Optimal?
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999
Graph Isomorphism is Low for ZPPNP and other Lowness results.
Electronic Colloquium on Computational Complexity (ECCC), 1999

The Complexity of Generating Test Instances.
Chicago J. Theor. Comput. Sci., 1999

1998
New Collapse Consequences of NP Having Small Circuits.
SIAM J. Comput., 1998

Average-Case Intractability vs. Worst-Case Intractability
Electronic Colloquium on Computational Complexity (ECCC), 1998

Average-Case Intractability vs. Worst-Case Intractability.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

On the Resource Bounded Measure of P/poly.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
The Complexity of Generating Test Instances.
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.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1997

High Sets for NP.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

Oracles in Sigmap2 are Sufficient for Exact Learning.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996
On the Power of Generalized MOD-Classes.
Mathematical Systems Theory, 1996

Upper Bounds for the Complexity of Sparse and Tally Descriptions.
Mathematical Systems Theory, 1996

Monotonous and Randomized Reductions to Sparse Sets.
ITA, 1996

1995
If NP has Polynomial-Size Circuits, then MA=AM.
Theor. Comput. Sci., 1995

The Power of the Middle Bit of a #P Function.
J. Comput. Syst. Sci., 1995

On Reductions to Sets that Avoid EXPSPACE.
Inf. Process. Lett., 1995

On Helping and Interactive Proof Systems.
Int. J. Found. Comput. Sci., 1995

New Collapse Consequences of NP Having Small Circuits.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

On the Structure of Low Sets.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
Locating P/poly Optimally in the Extended Low Hierarchy.
Theor. Comput. Sci., 1994

Complexity-Restricted Advice Functions.
SIAM J. Comput., 1994

On Helping and Interactive Proof Systems.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993
Locating P/poly Optimally in the Extended Low Hierarchy.
Proceedings of the STACS 93, 1993

Hausdorff Reductions to Sparse Sets and to Sets of High Information Content.
Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

On the Power of Generalized MOD-Classes.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Turing Machines with Few Accepting Computations and Low Sets for PP.
J. Comput. Syst. Sci., 1992

Graph Isomorphism is Low for PP.
Computational Complexity, 1992

Graph Isomorphism is Low for PP.
Proceedings of the STACS 92, 1992

Lowness and the Complexity of Sparse and Tally Descriptions.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

Reductions to Sets of Low Information Content.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

Reductions to Sets of Low Information Content.
Proceedings of the Complexity Theory: Current Research, 1992

The Power of the Middle Bit.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1990
Complexity Classes with Advice.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
On Counting and Approximation.
Acta Inf., 1989

Turing Machines with few Accepting Computations and low Sets for PP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

Strukturelle Komplexität von Anzahlproblemen.
PhD thesis, 1989

1988
On Counting and Approximation.
Proceedings of the CAAP '88, 1988

1987
The Difference and Truth-Table Hierarchies for NP.
ITA, 1987


  Loading...