Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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