Publikationen von Prof. Köbler
Veröffentlichungen in Journalen und Konferenzbeiträge
The Complexity of Learning Concept Classes with Polynomial General Dimension [ comp-gdim.pdf]
Johannes Köbler and Wolfgang Lindner
Theoretical Computer Science (TCS) 350, 49-62, 2006.
Extended abstract in Proceedings 13th International Workshop on Algorithmic Learning Theory (ALT'02), Springer-Verlag, Lecture Notes in Artificial Intelligence, LNAI 2533, 149-163, 2002.On Graph Isomorphism for Restricted Graph Classes [ cie-gi.pdf]
Johannes Köbler
Invited at Computability in Europe (CiE) 2006, Logical Approaches to Computational Barriers, special session on Challenges in Complexity, to appear.On Hypergraph and Graph Isomorphism with Bounded Color Classes [ hgi.pdf]
V. Arvind and Johannes Köbler
Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 3884, 384-395, 2006.Von der Turingmaschine zum Quantencomputer [ turing.pdf]
J. Köbler, O. Beyersdorff
Themen der Informatik im historischen Kontext, Springer Verlag, 2006.
Average-Case Intractability vs. Worst-Case Intractability [ average.ps.gz]
Johannes Köbler and Rainer Schuler
Information and Computation 190(1), 1-17, 2004.
Completeness Results for Graph Isomorphism [ comp-gi.ps.gz]
Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán
Journal of Computer and System Sciences (JCSS) 66, 549-566, 2003.
Optimal proof systems imply complete sets for promise classes [ opt-proof.ps.gz]
Johannes Köbler, Jochen Messner and Jacobo Torán
Information and Computation 184, 71-92, 2003.
A General Dimension for Approximate Learning [ gdim.ps.gz]
Johannes Köbler and Wolfgang Lindner
In Proceedings 13th International Workshop on Algorithmic Learning Theory (ALT'02), Springer-Verlag, Lecture Notes in Artificial Intelligence, LNAI 2533, 139-148, 2002.The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3 [ gi-color.ps.gz]
J. Köbler and J. Torán
Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 2285, 121-132, 2002.New Lowness Results for ZPP(NP) and other Complexity Classes [ zpp.ps.gz]
V. Arvind and Johannes Köbler
Journal of Computer and System Sciences (JCSS), 65(2): 257-277, 2002.
Extended abstract in Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 1770, 431-442, 2000.
On Pseudorandomness and Resource-Bounded Measure [ pseudorandom.ps.gz]
V. Arvind and Johannes Köbler
Theoretical Computer Science (TCS) 255 (1-2), 205-221, 2001.
Extended abstract in Proceedings 17th Conference on the Foundations of Software Technology & Theoretical Computer Science (FST&TCS), Springer-Verlag, LNCS 1346, 235-249, 1997.
Oracles in NP(NP) are sufficient for exact learning [ learning.ps.gz]
J. Köbler and W. Lindner
International Journal of Foundations of Computer Science (IJFOCS) 11(4), 615-632, 2000.
Extended abstract in Proceedings 8th International Workshop on Algorithmic Learning Theory (ALT'97), Springer-Verlag, LNAI 1316, 277-290, 1997.On distribution-specific learning with membership queries versus pseudorandom generation [ pwm.ps.gz]
J. Köbler and W. Lindner
Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2000.Is the Standard Proof System for SAT P-optimal? [ bsat.ps.gz]
J. Köbler and J. Messner
Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2000.Nondeterministic instance complexity and hard-to-prove tautologies [ nic.ps.gz]
V. Arvind, J. Köbler, M. Mundhenk and J. Torán
Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 1770, 314-323, 2000.
The Complexity of Generating Test Instances [ test.ps.gz]
C. Karg, J. Köbler and R. Schuler
Chicago Journal of Theoretical Computer Science 4:1-29, 1999.
Extended abstract in Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 1200, 375-386, 1997.
New Collapse Consequences of NP Having Small Circuits [ collapse.ps.gz]
J. Köbler and O. Watanabe
SIAM Journal on Computing, 28:311-324, 1998.
Extended abstract in International Colloquium on Automata, Languages and Programming (ICALP), Springer-Verlag, LNCS 944, 196-207, 1995.Average-Case Intractability vs. Worst-Case Intractability [ ap.ps.gz]
Johannes Köbler and Rainer Schuler
Proceedings of the Conference on Mathematical Foundations of Computer Sciences (MFCS),
Springer-Verlag, LNCS 1450, 493-502, 1998.On the Resource Bounded Measure of P/poly [ expnp.ps.gz]
Johannes Köbler and Wolfgang Lindner
Proceedings 13th IEEE Conference on Computational Complexity (CCC), 132-140, 1998.Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets [ opt.ps.gz]
Johannes Köbler and Jochen Meßner
Proceedings 13th IEEE Conference on Computational Complexity (CCC), 182-185, 1998.
High Sets for NP [ high.ps.gz]
Johannes Köbler and Uwe Schöning
In: D.-Z. Du, K.-I Ko (eds.), Advances in Languages, Algorithms, and Complexity. Kluwer Academic Publishers, 139-156, 1997.
Upper Bounds for the Complexity of Sparse and Tally Descriptions [ sparse.ps.gz]
Vikraman Arvind, Johannes Köbler, and Martin Mundhenk
Mathematical System Theory (MST) 29, 63-94, 1996.Monotonous and Randomized Reductions to Sparse Sets [ monotone.ps.gz]
Vikraman Arvind, Johannes Köbler, and Martin Mundhenk
RAIRO Theoretical Informatics and Applications 30(2), 155-179, 1996.
Extended abstract in Proceedings 17th Conference on the Foundations of Software Technology & Theoretical Computer Science (FST&TCS), Springer-Verlag, LNCS 652, 140-151, 1992.On the Power of Generalized MOD-Classes [ mod.ps.gz]
Johannes Köbler and Seinosuke Toda
Mathematical System Theory (MST) 29, 33-46, 1996.
Extended abstract in Proceedings 8th Structure in Complexity Theory Conference, 147-155, IEEE Computer Society, 1993.
On the Structure of Low Sets (Survey) [ low.ps.gz]
Johannes Köbler
Proceedings 10th Structure in Complexity Theory Conference, 246-261, IEEE Computer Society, 1995.On Reductions to Sets that Avoid EXPSPACE [ avoid.ps.gz]
Vikraman Arvind, Johannes Köbler, and Martin Mundhenk
Information Processing Letters (IPL) 56, 109-114, 1995.If NP has Polynomial-Size Circuits, then MA = AM [ ma-am.ps.gz]
Vikraman Arvind, Johannes Köbler, Uwe Schöning, and Rainer Schuler
Theoretical Computer Science (TCS) 137, 279-282, 1995.The Power of the Middle Bit of a #P Function [ middle.ps.gz]
Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, and Jacobo Torán
Journal of Computer and System Sciences (JCSS) 50(3), 456-467, 1995.
Extended abstract in Proceedings 7th Structure in Complexity Theory Conference, 111-117, IEEE Computer Society, 1992.
Locating P/poly Optimally in the Extended Low Hierarchy [ extlow.ps.gz]
Johannes Köbler
Theoretical Computer Science (TCS) 134, 263-285, 1994.
Extended abstract in Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 665, 28-37, 1993.On Helping and Interactive Proof Systems [ helping.ps.gz]
Vikraman Arvind, Johannes Köbler, and Rainer Schuler
International Journal of Foundations of Computer Science (IJFOCS) 6(2), 137-153, 1994.
Extended abstract in International Symposium on Algorithms and Computation (ISAAC), Springer-Verlag, LNCS 650, 249-258, 1992.Extension of Toda's Theorem to Middle Bit Classes (Survey) [ midbit.ps.gz]
Johannes Köbler
Workshop on Algebraic Methods in Complexity Theory, Technical Report IMSc-94/51, 39-57, 1994.Complexity-Restricted Advice Functions [ advice.ps.gz]
Johannes Köbler and Thomas Thierauf
SIAM Journal on Computing 23(2), 261-275, 1994.
Extended abstract in Proceedings 5th Structure in Complexity Theory Conference, 305-315, IEEE Computer Society, 1990.
Hausdorff Reductions to Sparse Sets and to Sets of High Information Content [ hausdorff.ps.gz]
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
Conference on Mathematical Foundations of Computer Sciences (MFCS),
Springer-Verlag, LNCS 711, 232-241, 1993.Reductions to Sets of Low Information Content [ URTR-417.ps.gz]
V.Arvind, Y. Han, L. Hamachandra, J. Köbler, A. Lozano, M. Mundhenk, A. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf
(Here you find the full version which is University of Rochester TR 417, 1992.)
In: K. Ambos-Spies, S. Homer, and U. Schöning (eds.), Recent Developments in Complexity Theory. Cambridge University Press, 1993.
Extended abstract in Proceedings 19th International Colloquium on Automata, Languages and Programming (ICALP), Springer-Verlag, LNCS 623, 162-173, 1992.
On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets [ random.ps.gz]
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
Conference on the Foundations of Software Technology & Theoretical Computer Science (FST&TCS),
Springer-Verlag, LNCS 652, 140-151, 1992.Turing Machines with Few Accepting Computations and Low Sets for PP [ few.ps.gz]
Johannes Köbler, Uwe Schöning, Seinosuke Toda, and Jacobo Torán
Journal of Computer and System Sciences (JCSS) 44(2), 272-286, 1992.
Extended abstract in Proceedings 4th Structure in Complexity Theory Conference, 208-215, IEEE Computer Society, 1989.Graph Isomorphism is Low for PP [ gi.ps.gz]
Johannes Köbler, Uwe Schöning, and Jacobo Torán
Journal of Computational Complexity 2, 301-330, 1992.
Extended abstract in Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, LNCS 577, 401-411, 1992.Lowness and the Complexity of Sparse and Tally Descriptions [ lowness.ps.gz]
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
International Symposium on Algorithms and Computation (ISAAC),
Springer-Verlag, LNCS 650, 249-258, 1992.
On Counting and Approximation
Johannes Köbler, Uwe Schöning, and Jacobo Torán
Acta Informatica 26, 363-379, 1989.
Extended abstract in Proceedings 13th Colloquium on Trees in Algebra and Programming, Springer-Verlag, LNCS 299, 40-51, 1988.
The Difference and Truth-Table Hierarchies for NP
Johannes Köbler, Uwe Schöning, and Klaus Wagner
RAIRO Theoretical Informatics and Applications 21(4), 419-435, 1987.
Bücher und sonstige Arbeiten
The Graph Isomorphism Problem: Its Structural Complexity
Johannes Köbler, Uwe Schöning, and Jacobo Torán
Habilitationsschrift: Lowness-Eigenschaften und Erlernbarkeit von Booleschen Schaltkreisklassen
Johannes Köbler
Dissertation: Strukturelle Komplexität von Anzahlproblemen
Johannes Köbler