Johannes Koebler
Johannes Koebler
Professor of Theoretical Computer Science, Humboldt-University Berlin
Verified email at informatik.hu-berlin.de - Homepage
Title
Cited by
Cited by
Year
The graph isomorphism problem: its structural complexity
J Kobler, U Schöning, J Torán
Springer Science & Business Media, 2012
6502012
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
1721987
New collapse consequences of NP having small circuits
J Köbler, O Watanabe
SIAM Journal on Computing 28 (1), 311-324, 1998
1291998
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
1001992
On counting and approximation
J Köbler, U Schöning, J Torán
Acta Informatica 26 (4), 363-379, 1989
891989
Graph isomorphism is low for PP
J Köbler, U Schöning, J Torán
Computational Complexity 2 (4), 301-330, 1992
821992
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
762003
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
701992
On pseudorandomness and resource-bounded measure
V Arvind, J Köbler
Theoretical Computer Science 255 (1-2), 205-221, 2001
63*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
562003
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
511995
Locating P/poly optimally in the extended low hierarchy
J Köbler
Theoretical Computer Science 134 (2), 263-285, 1994
421994
Approximate graph isomorphism
V Arvind, J Köbler, S Kuhnert, Y Vasudev
International Symposium on Mathematical Foundations of Computer Science, 100-111, 2012
362012
Interval graphs: Canonical representations in logspace
J Köbler, S Kuhnert, B Laubner, O Verbitsky
SIAM Journal on Computing 40 (5), 1292-1315, 2011
352011
On resource-bounded measure and pseudorandomness
V Arvind, J Köbler
International Conference on Foundations of Software Technology and …, 1997
351997
Strukturelle Komplexität von Anzahlproblemen
J Köbler
Universität Stuttgart, 1989
341989
On graph isomorphism for restricted graph classes
J Köbler
Conference on Computability in Europe, 241-256, 2006
332006
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
331992
On the structure of low sets [complexity classes]
J Kobler
Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference …, 1995
311995
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
292015
The system can't perform the operation now. Try again later.
Articles 1–20