|
|
2006
Vertrauenswürdige Chipkartenbasierte Biometrische Authentifikation [CBI.pdf]
G. Lassmann, M. Schwan
Jahrestagung der Gesellschaft für Informatik, Fachbereich Sicherheit, Magdeburg
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]2002
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]2001
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 Learning Concept Classes with Polynomial General Dimension [comp-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, 149-163, 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]2000
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]1999
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 Asymptotic Power and Relative Efficiency of some c-Sample Rank Tests of Homogeneity against Umbrella Alternatives [Umbrella.pdf]
W. Kössler und H. Büning
Statistics, Vol. 34, No. 1, 2000, 1-26The Efficiency of some c-Sample Rank tests of Homogeneity against ordered Alternatives [Nonparametric_Statistics.pdf]
W. Kössler und H. Büning
Journal of Nonparametric Statistics 13, 2000, 95-106
The Complexity of Generating Test Instances [test.ps.gz]1998
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]1997
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]1996
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]1995
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]1994
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]1993
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]1992
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]1989
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 Approximation1987
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.
|
|
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