Johannes Köbler
According to our database1, Johannes Köbler
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
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
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.
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.
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