default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJohannes Köbler
Person information
- affiliation: Humboldt University of Berlin, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c56]Vikraman Arvind, Frank Fuhlbrück
, Johannes Köbler, Oleg Verbitsky:
On a Hierarchy of Spectral Invariants for Graphs. STACS 2024: 6:1-6:18- [i27]Vikraman Arvind, Johannes Köbler, Oleg Verbitsky:
On the Expressibility of the Reconstructional Color Refinement. CoRR abs/2406.09351 (2024) - 2023
- [i26]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On a Hierarchy of Spectral Isomorphism Invariants. CoRR abs/2310.04391 (2023) - 2022
- [j48]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On the Weisfeiler-Leman dimension of fractional packing. Inf. Comput. 288: 104803 (2022) - [j47]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan:
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. ACM Trans. Comput. Theory 14(2): 9:1-9:26 (2022) - 2021
- [j46]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms and Isomorphisms. Algorithmica 83(12): 3567-3601 (2021) - [j45]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Local WL invariance and hidden shades of regularity. Discret. Appl. Math. 305: 191-198 (2021) - [j44]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. SIAM J. Discret. Math. 35(3): 1792-1853 (2021) - [j43]Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky:
The Weisfeiler-Leman algorithm and recognition of graph properties. Theor. Comput. Sci. 895: 96-114 (2021) - [c55]Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky:
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CIAC 2021: 245-257 - 2020
- [j42]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci. 113: 42-59 (2020) - [c54]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On the Weisfeiler-Leman Dimension of Fractional Packing. LATA 2020: 357-368 - [c53]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. STACS 2020: 43:1-43:18 - [i25]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Local WL Invariance and Hidden Shades of Regularity. CoRR abs/2002.04590 (2020) - [i24]Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky:
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CoRR abs/2005.08887 (2020)
2010 – 2019
- 2019
- [c52]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. FCT 2019: 111-125 - [i23]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. CoRR abs/1907.02892 (2019) - [i22]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On the Weisfeiler-Leman Dimension of Fractional Packing. CoRR abs/1910.11325 (2019) - 2018
- [i21]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. CoRR abs/1811.04801 (2018) - 2017
- [j41]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
Graph Isomorphism, Color Refinement, and Compactness. Comput. Complex. 26(3): 627-685 (2017) - [j40]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Circular-arc hypergraphs: Rigidity via connectedness. Discret. Appl. Math. 217: 220-228 (2017) - [c51]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. IPEC 2017: 2:1-2:13 - [c50]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms. STACS 2017: 7:1-7:13 - [i20]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. CoRR abs/1709.10063 (2017) - 2016
- [j39]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. Algorithmica 75(2): 322-338 (2016) - [j38]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
On the isomorphism problem for Helly circular-arc graphs. Inf. Comput. 247: 266-277 (2016) - [j37]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace. J. Discrete Algorithms 38-41: 38-49 (2016) - [c49]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan:
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. MFCS 2016: 13:1-13:14 - [i19]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan:
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. CoRR abs/1606.04383 (2016) - [i18]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j36]Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda:
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. Algorithmica 71(1): 120-138 (2015) - [j35]Johannes Köbler, Jacobo Torán:
Lowness results: the next generation. Bull. EATCS 117 (2015) - [j34]Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. J. Discrete Algorithms 34: 108-117 (2015) - [j33]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev:
On the isomorphism problem for decision trees and decision lists. Theor. Comput. Sci. 590: 38-54 (2015) - [c48]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
On the Power of Color Refinement. FCT 2015: 339-350 - [c47]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
On Tinhofer's Linear Programming Approach to Isomorphism Testing. MFCS (2) 2015: 26-37 - [i17]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
Graph Isomorphism, Color Refinement, and Compactness. CoRR abs/1502.01255 (2015) - [i16]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
Graph Isomorphism, Color Refinement, and Compactness. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c46]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. IPEC 2014: 39-50 - [i15]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
On the Isomorphism Problem for Helly Circular-Arc Graphs. CoRR abs/1402.4642 (2014) - [i14]Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j32]Vikraman Arvind, Johannes Köbler:
The Parallel Complexity of Graph Canonization Under Abelian Group Action. Algorithmica 67(2): 247-276 (2013) - [c45]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev:
On the Isomorphism Problem for Decision Trees and Decision Lists. FCT 2013: 16-27 - [c44]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Helly Circular-Arc Graph Isomorphism Is in Logspace. MFCS 2013: 631-642 - [i13]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Circular-arc hypergraphs: Rigidity via Connectedness. CoRR abs/1312.1172 (2013) - [i12]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Helly Circular-Arc Graph Isomorphism is in Logspace. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j31]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Around and Beyond the Isomorphism Problem for Interval Graphs. Bull. EATCS 107: 43-71 (2012) - [j30]Vikraman Arvind, Bireswar Das, Johannes Köbler, Sebastian Kuhnert:
The isomorphism problem for k-trees is complete for logspace. Inf. Comput. 217: 1-11 (2012) - [c43]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace. FSTTCS 2012: 387-399 - [c42]Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe:
Interval Graph Representation with Given Interval and Intersection Lengths. ISAAC 2012: 517-526 - [c41]Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Yadu Vasudev:
Approximate Graph Isomorphism. MFCS 2012: 100-111 - [i11]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space. CoRR abs/1202.4406 (2012) - [i10]Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev:
Approximate Graph Isomorphism. Electron. Colloquium Comput. Complex. TR12 (2012) - [i9]Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j29]Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
Proof systems that take advice. Inf. Comput. 209(3): 320-332 (2011) - [j28]Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky:
Interval Graphs: Canonical Representations in Logspace. SIAM J. Comput. 40(5): 1292-1315 (2011) - [c40]Vikraman Arvind, Johannes Köbler:
Canonizing Hypergraphs under Abelian Group Action. COCOON 2011: 444-455 - 2010
- [c39]Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda:
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. FSTTCS 2010: 327-337 - [c38]Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace. ICALP (1) 2010: 384-395 - [i8]Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j27]Olaf Beyersdorff, Johannes Köbler, Jochen Messner:
Nondeterministic functions and the existence of optimal proof systems. Theor. Comput. Sci. 410(38-40): 3839-3855 (2009) - [j26]Vikraman Arvind, Johannes Köbler, Wolfgang Lindner:
Parameterized learnability of juntas. Theor. Comput. Sci. 410(47-49): 4928-4936 (2009) - [c37]Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
Nondeterministic Instance Complexity and Proof Systems with Advice. LATA 2009: 164-175 - [c36]Johannes Köbler, Sebastian Kuhnert:
The Isomorphism Problem for k-Trees Is Complete for Logspace. MFCS 2009: 537-548 - [i7]Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda:
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. Electron. Colloquium Comput. Complex. TR09 (2009) - [i6]Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
Proof Systems that Take Advice. Electron. Colloquium Comput. Complex. TR09 (2009) - [i5]Johannes Köbler, Sebastian Kuhnert:
The Isomorphism Problem for k-Trees is Complete for Logspace. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c35]Vikraman Arvind, Bireswar Das, Johannes Köbler:
A Logspace Algorithm for Partial 2-Tree Canonization. CSR 2008: 40-51 - [c34]Johannes Köbler, Oleg Verbitsky:
From Invariants to Canonization in Parallel. CSR 2008: 216-227 - [i4]Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
Nondeterministic Instance Complexity and Proof Systems with Advice. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j25]José L. Balcázar, Jorge Castro, David Guijarro, Johannes Köbler, Wolfgang Lindner:
A general dimension for query learning. J. Comput. Syst. Sci. 73(6): 924-940 (2007) - [c33]Vikraman Arvind, Johannes Köbler, Wolfgang Lindner:
Parameterized Learnability of k -Juntas and Related Problems. ALT 2007: 120-134 - [c32]Vikraman Arvind, Bireswar Das, Johannes Köbler:
The Space Complexity of k -Tree Isomorphism. ISAAC 2007: 822-833 - 2006
- [j24]Johannes Köbler, Wolfgang Lindner:
Learning Boolean Functions under the Uniform. Bull. EATCS 89: 48-78 (2006) - [j23]Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán:
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566]. J. Comput. Syst. Sci. 72(4): 783 (2006) - [j22]Johannes Köbler, Wolfgang Lindner:
The complexity of learning concept classes with polynomial general dimension. Theor. Comput. Sci. 350(1): 49-62 (2006) - [c31]Johannes Köbler:
On Graph Isomorphism for Restricted Graph Classes. CiE 2006: 241-256 - [c30]Vikraman Arvind, Johannes Köbler:
On Hypergraph and Graph Isomorphism with Bounded Color Classes. STACS 2006: 384-395 - [i3]Johannes Köbler, Oleg Verbitsky:
From Invariants to Canonization in Parallel. CoRR abs/cs/0608074 (2006) - 2004
- [j21]Johannes Köbler, Rainer Schuler:
Average-case intractability vs. worst-case intractability. Inf. Comput. 190(1): 1-17 (2004) - 2003
- [j20]Johannes Köbler, Jochen Messner, Jacobo Torán:
Optimal proof systems imply complete sets for promise classes. Inf. Comput. 184(1): 71-92 (2003) - [j19]Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán:
Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66(3): 549-566 (2003) - 2002
- [j18]Vikraman Arvind, Johannes Köbler:
New Lowness Results for ZPPNP and Other Complexity Classes. J. Comput. Syst. Sci. 65(2): 257-277 (2002) - [c29]Johannes Köbler, Wolfgang Lindner:
A General Dimension for Approximately Learning Boolean Functions. ALT 2002: 139-148 - [c28]Johannes Köbler, Wolfgang Lindner:
The Complexity of Learning Concept Classes with Polynomial General Dimension. ALT 2002: 149-163 - [c27]Johannes Köbler, Jacobo Torán:
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3. STACS 2002: 121-132 - 2001
- [j17]Vikraman Arvind, Johannes Köbler:
On pseudorandomness and resource-bounded measure. Theor. Comput. Sci. 255(1-2): 205-221 (2001) - 2000
- [j16]Johannes Köbler, Wolfgang Lindner:
Oracles in Sp2 are Sufficient for Exact Learning. Int. J. Found. Comput. Sci. 11(4): 615-632 (2000) - [c26]Johannes Köbler, Wolfgang Lindner:
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation. FSTTCS 2000: 336-347 - [c25]Johannes Köbler, Jochen Messner:
Is the Standard Proof System for SAT P-Optimal? FSTTCS 2000: 361-372 - [c24]Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán:
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. STACS 2000: 314-323 - [c23]Vikraman Arvind, Johannes Köbler:
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. STACS 2000: 431-442
1990 – 1999
- 1999
- [j15]Christoph Karg, Johannes Köbler, Rainer Schuler:
The Complexity of Generating Test Instances. Chic. J. Theor. Comput. Sci. 1999 (1999) - [i2]Vikraman Arvind, Johannes Köbler:
Graph Isomorphism is Low for ZPPNP and other Lowness results. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j14]Johannes Köbler, Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits. SIAM J. Comput. 28(1): 311-324 (1998) - [c22]Johannes Köbler, Jochen Messner:
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. CCC 1998: 132-140 - [c21]Johannes Köbler, Wolfgang Lindner:
On the Resource Bounded Measure of P/poly. CCC 1998: 182-185 - [c20]Johannes Köbler, Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability. MFCS 1998: 493-502 - [i1]Johannes Köbler, Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [c19]Johannes Köbler, Wolfgang Lindner:
Oracles in Sigmap2 are Sufficient for Exact Learning. ALT 1997: 277-290 - [c18]Johannes Köbler, Uwe Schöning:
High Sets for NP. Advances in Algorithms, Languages, and Complexity 1997: 139-156 - [c17]Vikraman Arvind, Johannes Köbler:
On Resource-Bounded Measure and Pseudorandomness. FSTTCS 1997: 235-249 - [c16]Christoph Karg, Johannes Köbler, Rainer Schuler:
The Complexity of Generating Test Instances. STACS 1997: 375-386 - 1996
- [j13]Vikraman Arvind, Johannes Köbler, Martin Mundhenk:
Monotonous and Randomized Reductions to Sparse Sets. RAIRO Theor. Informatics Appl. 30(2): 155-179 (1996) - [j12]Johannes Köbler, Seinosuke Toda:
On the Power of Generalized MOD-Classes. Math. Syst. Theory 29(1): 33-46 (1996) - [j11]Vikraman Arvind, Johannes Köbler, Martin Mundhenk:
Upper Bounds for the Complexity of Sparse and Tally Descriptions. Math. Syst. Theory 29(1): 63-94 (1996) - 1995
- [j10]Vikraman Arvind, Johannes Köbler, Rainer Schuler:
On Helping and Interactive Proof Systems. Int. J. Found. Comput. Sci. 6(2): 137-153 (1995) - [j9]Vikraman Arvind, Johannes Köbler, Martin Mundhenk:
On Reductions to Sets that Avoid EXPSPACE. Inf. Process. Lett. 56(2): 109-114 (1995) - [j8]Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán:
The Power of the Middle Bit of a #P Function. J. Comput. Syst. Sci. 50(3): 456-467 (1995) - [j7]Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler:
If NP has Polynomial-Size Circuits, then MA=AM. Theor. Comput. Sci. 137(2): 279-282 (1995) - [c15]Johannes Köbler:
On the Structure of Low Sets. SCT 1995: 246-261 - [c14]Johannes Köbler, Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits. ICALP 1995: 196-207 - 1994
- [j6]Johannes Köbler, Thomas Thierauf:
Complexity-Restricted Advice Functions. SIAM J. Comput. 23(2): 261-275 (1994) - [j5]Johannes Köbler:
Locating P/poly Optimally in the Extended Low Hierarchy. Theor. Comput. Sci. 134(2): 263-285 (1994) - [c13]Vikraman Arvind, Johannes Köbler, Rainer Schuler:
On Helping and Interactive Proof Systems. ISAAC 1994: 137-145 - 1993
- [b2]Johannes Köbler, Uwe Schöning, Jacobo Torán:
The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science, Birkhäuser/Springer 1993, ISBN 978-1-4612-6712-6 - [c12]Johannes Köbler, Seinosuke Toda:
On the Power of Generalized MOD-Classes. SCT 1993: 147-155 - [c11]Vikraman Arvind, Johannes Köbler, Martin Mundhenk:
Hausdorff Reductions to Sparse Sets and to Sets of High Information Content. MFCS 1993: 232-241 - [c10]Johannes Köbler:
Locating P/poly Optimally in the Extended Low Hierarchy. STACS 1993: 28-37 - 1992
- [j4]Johannes Köbler, Uwe Schöning, Jacobo Torán:
Graph Isomorphism is Low for PP. Comput. Complex. 2: 301-330 (1992) - [j3]