Veröffentlichungen in Journalen und Konferenzbeiträge

2008

From Invariants to Canonization in Parallel
Johannes Köbler, Oleg Verbitsky
CSR 2008: 216-227

A Logspace Algorithm for Partial 2-Tree Canonization.
Vikraman Arvind, Bireswar Das, Johannes Köbler
CSR 2008: 40-51

Nondeterministic Instance Complexity and Proof Systems with Advice
Olaf Beyersdorff, Sebastian Müller, Johannes Köbler
Preprint.

A Tight Karp-Lipton Collapse for Bounded Arithmetic (extended abstract)
Olaf Beyersdorff, Sebastian Müller
Proc. 17th EACSL Annual Conference on Computer Science Logic (CSL), To appear.

On the Correspondence Between Arithmetic Theories and Propositional Proof Systems - a Survey
Olaf Beyersdorff
Mathematical Logic Quarterly, To appear.

Logical Closure Properties of Propositional Proof Systems(Extended Abstract)
Olaf Beyersdorff
Proc. 5th Annual Conference on Theory and Applications of Models of Computation (TAMC), LNCS 4978, To appear.

Tuples of Disjoint NP-Sets [tuples_journal.pdf]
Olaf Beyersdorff
Theory of Computing Systems, To appear.

2007

A General Dimension for Query Learning [gdim.pdf]
J. L. Balcàzar, J. Castro, D. Guijarro, J. Köbler, W. Lindner
Journal of Computer and System Sciences (JCSS), 73(6): 924-940, 2007.

Parameterized Learnability of k-Juntas and Related Problems [juntas.pdf]
V. Arvind, J. Köbler, W. Lindner
Proceedings 13th Intern. Conf. on Algorithmic Learning Theory (ALT), Springer-Verlag, LNCS 4754, 120-134, 2007.

The Space Complexity of k-Tree Isomorphism [ktree.pdf]
V. Arvind, B. Das, J. Köbler
Proc. 18th Intern. Symp. on Algorithms and Computation (ISAAC), Springer-Verlag, LNCS 4835, 822-833, 2007.

The Deduction Theorem for Strong Propositional Proof Systems [delhi_final.pdf]
Olaf Beyersdorff
Proc. 27th Conference on Foundations of Software Technology & Theoretical
Computer Science (FST&TCS), LNCS 4855, Pages 241-252, 2007.

Classes of Representable Disjoint NP-Pairs [dnpp_tcs_final.pdf]
Olaf Beyersdorff
Theoretical Computer Science, Volume 377, Issues 1-3, Pages 93-109, 2007.

2006

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] (revision available)
Johannes Köbler
Proceedings Second Conference on Computability in Europe (CiE) 2006, Logical Approaches to Computational Barriers, Springer-Verlag, LNCS 3988, 241-256, 2006.

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.

Vertrauenswüdige Chipkartenbasierte Biometrische Authentifikation [CBI.pdf]
G. Lassmann, M. Schwan
Jahrestagung der Gesellschaft für Informatik, Fachbereich Sicherheit, Magdeburg

Disjoint NP Pairs from propositional proof systems [dnpp06_1.pdf]
O. Beyersdorff
Proc. 3rd Conference on Theory and Applications of Models of Computation, Springer Verlag, LNCS 3959, 236-247, 2006.

Tuples of Disjoint NP-Sets [dnpp06_2.pdf]
O. Beyersdorff
Proc. 1st International Computer Science Symposium in Russia, Springer Verlag, LNCS 3967, 80-91, 2006.

Von der Turingmaschine zum Quantencomputer [turing.pdf]
J. Köbler, O. Beyersdorff
Themen der Informatik im historischen Kontext, Springer Verlag, 2006.

2005

Secure Biometric Identification System [Verisoft.pdf]
G. Lassmann, G. Rock und M. Schwan
T-Systems International University Conference, Duesseldorf

2004

Average-Case Intractability vs. Worst-Case Intractability [average.ps.gz]
Johannes Köbler and Rainer Schuler
Information and Computation 190(1), 1-17, 2004.

Representable Disjoint NP-Pairs [dnpp.ps.gz]
Olaf Beyersdorff
In Proceedings 24th Conference on the Foundations of Software Technology & Theoretical Computer Science (FST&TCS), Springer-Verlag, LNCS  3328, 122-1344, 2004.

2003

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.

2002

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.

2001

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.

2000

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.

1999

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.

1998

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.

1997

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.

1996

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.

1995

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.

1994

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.

1993

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.

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.

1989

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.

1987

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