Johannes Koebler
Johannes Koebler
Professor of Theoretical Computer Science, Humboldt-University Berlin
Verified email at - Homepage
Cited by
Cited by
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-Informatique Théorique et …, 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
On counting and approximation
J Köbler, U Schöning, J Torán
Acta Informatica 26 (4), 363-379, 1989
Graph isomorphism is low for PP
J Köbler, U Schöning, J Torán
Computational Complexity 2 (4), 301-330, 1992
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, ...
International Colloquium on Automata, Languages, and Programming, 162-173, 1992
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
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
Locating P/poly optimally in the extended low hierarchy
J Köbler
Theoretical Computer Science 134 (2), 263-285, 1994
Approximate graph isomorphism
V Arvind, J Köbler, S Kuhnert, Y Vasudev
International Symposium on Mathematical Foundations of Computer Science, 100-111, 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
On resource-bounded measure and pseudorandomness
V Arvind, J Köbler
International Conference on Foundations of Software Technology and …, 1997
Strukturelle Komplexität von Anzahlproblemen
J Köbler
Universität Stuttgart, 1989
On graph isomorphism for restricted graph classes
J Köbler
Conference on Computability in Europe, 241-256, 2006
On bounded truth-table, conjunctive, and randomized reductions to sparse sets
V Arvind, J Köbler, M Mundhenk
International Conference on Foundations of Software Technology and …, 1992
On the structure of low sets [complexity classes]
J Kobler
Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference …, 1995
On the power of color refinement
V Arvind, J Köbler, G Rattan, O Verbitsky
International Symposium on Fundamentals of Computation Theory, 339-350, 2015
The system can't perform the operation now. Try again later.
Articles 1–20