Johannes Koebler
Johannes Koebler
Professor of Theoretical Computer Science, Humboldt-University Berlin
Dirección de correo verificada de - Página principal
Citado por
Citado por
The graph isomorphism problem: its structural complexity
J Kobler, U Schöning, J Torán
Springer Science & Business Media, 2012
The difference and truth-table hierarchies for NP
J Köbler, U Schöning, KW Wagner
RAIRO-Theoretical Informatics and Applications 21 (4), 419-435, 1987
New collapse consequences of NP having small circuits
J Köbler, O Watanabe
SIAM Journal on Computing 28 (1), 311-324, 1998
Turing machines with few accepting computations and low sets for PP
J Köbler, U Schöning, S Toda, J Torán
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät …, 1992
Graph isomorphism is low for PP
J Köbler, U Schöning, J Torán
Computational Complexity 2, 301-330, 1992
On counting and approximation
J Köbler, U Schöning, J Torán
Acta Informatica 26, 363-379, 1989
Completeness results for graph isomorphism
B Jenner, J Köbler, P McKenzie, J Torán
Journal of Computer and System Sciences 66 (3), 549-566, 2003
Reductions to sets of low information content
V Arvind, Y Han, L Hemachandra, J Köbler, A Lozano, M Mundhenk, ...
Automata, Languages and Programming: 19th International Colloquium Wien …, 1992
On weisfeiler-leman invariance: Subgraph counts and related graph properties
V Arvind, F Fuhlbrück, J Köbler, O Verbitsky
Journal of Computer and System Sciences 113, 42-59, 2020
On pseudorandomness and resource-bounded measure
V Arvind, J Köbler
Theoretical Computer Science 255 (1-2), 205-221, 2001
Optimal proof systems imply complete sets for promise classes
J Köbler, J Messner, J Torán
Information and Computation 184 (1), 71-92, 2003
On the power of color refinement
V Arvind, J Köbler, G Rattan, O Verbitsky
Fundamentals of Computation Theory: 20th International Symposium, FCT 2015 …, 2015
The power of the middle bit of a# P function
F Green, J Kobler, KW Regan, T Schwentick, J Torán
Journal of Computer and System Sciences 50 (3), 456-467, 1995
Approximate graph isomorphism
V Arvind, J Köbler, S Kuhnert, Y Vasudev
Mathematical Foundations of Computer Science 2012: 37th International …, 2012
Interval graphs: Canonical representations in logspace
J Köbler, S Kuhnert, B Laubner, O Verbitsky
SIAM Journal on Computing 40 (5), 1292-1315, 2011
Locating P/poly optimally in the extended low hierarchy
J Köbler
Theoretical Computer Science 134 (2), 263-285, 1994
On resource-bounded measure and pseudorandomness
V Arvind, J Köbler
Foundations of Software Technology and Theoretical Computer Science: 17th …, 1997
On graph isomorphism for restricted graph classes
J Köbler
Conference on Computability in Europe, 241-256, 2006
Strukturelle Komplexität von Anzahlproblemen
J Köbler
Universität Stuttgart, 1989
On bounded truth-table, conjunctive, and randomized reductions to sparse sets
V Arvind, J Köbler, M Mundhenk
Foundations of Software Technology and Theoretical Computer Science: 12th …, 1992
El sistema no puede realizar la operación en estos momentos. Inténtalo de nuevo más tarde.
Artículos 1–20