Publikationen
Veröffentlichungen in Journalen und Konferenzbeiträge
2016
An adaptive test for the two-sample scale problem where the common quantile may be different from the median
Wolfgang Kössler.
Statistical Methodology 29: 10–17 (2016).
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan.
Mathematical Foundations of Computer Science (Proceedings of 41st MFCS). LIPIcs, 2016.
Solving Linear Equations Parameterized by Hamming Weight
V. Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán.
Algorithmica 75(2) (2016).
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky.
Journal of Descrete Algorithms 38 (2016).
On the isomorphism problem for Helly circular-arc graphs
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky.
Information and Computation 247: 266–277 (2016).
2015
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky.
ACM Transactions on Computational Logic (TOCL) 16(3): 21 (2015).
Colored Hypergraph Isomorphism is Fixed Parameter Tractable
V. Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda.
Algorithmica 71(1): 120-138 (2015).
Interval graph representation with given interval and intersection lengths
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe.
Journal of Discrete Algorithms 34: 108–117 (2015).
On the isomorphism problem for decision trees and decision lists
V. Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev.
Theoretical Computer Science 590: 38–54 (2015).
On the power of color refinement
V. Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky.
Fundamentals of Computation Theory (Proceedings of 20th FCT) Pp. 339–350 (2015).
On Tinhofer’s linear programming approach to isomorphism testing
V. Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky.
Mathematical Foundations of Computer Science (Proceedings of 40th MFCS) Pp. 26–37 (2015).
Variable inspection plans for continuous populations with unknown short tail distributions
Wolfgang Kössler.
Stochastic Models, Statistics and Their Applications. Pp. 93–100 (2015).
Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
Andreas Krebs, Oleg Verbitsky.
Logic in Computer Science (LICS). Pp. 689–700 (2015).
2014
Solving Linear Equations Parameterized by Hamming Weight
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán.
Parameterized and Exact Computation (Proceedings of 9th IPEC) Pp. 39-50. LNCS 8894.
2013
The Parallel Complexity of Graph Canonization Under Abelian Group Action
V. Arvind and Johannes Köbler.
Algorithmica 67(2): 247-276 (2013).
On the isomorphism problem for decision trees and decision lists
V. Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev.
Fundamentals of Computation Theory (Proceedings of 19th FCT). Pp. 16-27. LNCS 8070.
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Computer Science Logic 2013. Pp. 61-80. LIPIcs 23.
On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing
Christoph Berkholz, Oleg Verbitsky.
Mathematical Foundations of Computer Science (Proceedings of 38th MFCS). Pp. 159-170. LNCS 8087.
Helly Circular-Arc Graph Isomorphism is in logspace
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky.
Mathematical Foundations of Computer Science (Proceedings of 38th MFCS). Pp. 631-642. LNCS 8087.
2012
Interval graph representation with given interval and intersection lengths
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe.
Algorithms and Computation (Proceedings of 23rd ISAAC), pp. 517-526. LNCS 7676.
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky.
Proceedings of 32nd FSTTCS (2012). Pp. 387-399. LIPIcs 18.
Approximate Graph Isomorphism
V. Arvind, Johannes Köbler, Sebastian Kuhnert, Yadu Vasudev.
Mathematical Foundations of Computer Science 2012 (Proceedings of 37th MFCS), pp. 100-111. LNCS 7464.
Around and beyond the isomorphism problem for interval graphs
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky.
Bulletin of the EATCS 107 (2012), pp. 44-71.
The Isomorphism Problem for k-trees is Complete for Logspace
V. Arvind, Bireswar Das, Johannes Köbler, Sebastian Kuhnert
Information and Computation 217 (2012), pp. 1-11.
2011
Interval Graphs: Canonical Representations in Logspace
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
SIAM Journal on Computing 20.5 (2011), pp. 1292-1315.
Formation of translational risk score based on correlation coefficients as an alternative to Cox regression models for predicting outcome in patients with NSCLC.
W. Kössler, A. Fiebeler, A. Willms, T. El Aidi, B. Klosterhalfen, U. Klinge
Theoretical Biology and Medical Modelling , 2011, 8-28.
2010
Colored Hypergraph Isomorphism is Fixed Parameter Tractable
V. Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
Proc. Conference on Foundations of Software Technology & Theoretical Computer Science (FST&TCS), Leibniz International Proceedings in Informatics (LIPIcs) 8, Pages 327-337, 2010.
Proof Systems that Take Advice
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
To appear in Information and Computation.
Interval Graphs: Canonical Representation in Logspace
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Proceedings 37th International Colloquium on Automata, Languages and Programming (ICALP), Springer-Verlag, LNCS 6198, 384-395, 2010.
An adaptive test for the two-sample scale problem based on U-statistics.
W. Kössler, N. Kumar
Communications in Statistics - Computation and Simulation , Vol. 39, 2010, 1785-1802.
Max-Type Rank Tests, U-Tests, and Adaptive Tests for the Two-sample Location Problem - An Asymptotic Power Study
W. Kössler
Computational Statistics and Data Analysis , 54, 2010, 2053-2065.
Adaptive Lagetests mit U-Statistiken.
W. Kössler, W. F. Lesener
Proceedings der 14. Konferenz der SAS-Anwender in Forschung und Entwicklung , Freie Universität Berlin (ed. Rendtel, U.), 2010, Shaker-Verlag Aachen, 127-147.
2009
Parameterized Learnability of Juntas
V. Arvind, Johannes Köbler, Wolfgang Lindner
Theoretical Computer Science, Volume 410, Number 47 - 49, Pages 4928 - 4936, 2009.
Nondeterministic Functions and the Existence of Optimal Proof Systems
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Theoretical Computer Science, Volume 410, Number 38 - 40, Pages 3839 - 3855, 2009.
The Isomorphism Problem for k-Trees is Complete for Logspace
Johannes Köbler, Sebastian Kuhnert
Proceedings 34th Mathematical Foundations of Computer Science (MFCS), Springer-Verlag, LNCS 5734, 537-548, 2009.
Nondeterministic Instance Complexity and Proof Systems with Advice
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Proc. 3rd International Conference on Language and Automata Theory and Applications (LATA), Springer-Verlag, LNCS 5457, Pages 164 - 175, 2009.
2008
From Invariants to Canonization in Parallel
Johannes Köbler, Oleg Verbitsky
Proceedings 3rd International Computer Science Symposium in Russia (CSR), Springer-Verlag, LNCS 5010, 216-227, 2008.
A Logspace Algorithm for Partial 2-Tree Canonization.
V. Arvind, Bireswar Das, Johannes Köbler
Proceedings 3rd International Computer Science Symposium in Russia (CSR), Springer-Verlag, LNCS 5010, 40-51, 2008.
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.
An adaptive test for the two-sample location problem based on U-statistics.
W. Kössler, N. Kumar
Communications in Statistics - Computation and Simulation, Vol. 37, 2008, 1329-1346
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, MagdeburgDisjoint 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.The asymptotic efficacies and relative efficiencies for various linear rank tests for Independence.
W. Kössler, E. Rödel
Metrika, 2006
2005
Secure Biometric Identification System [Verisoft.pdf]
G. Lassmann, G. Rock und M. Schwan
T-Systems International University Conference, DuesseldorfSome c-Sample Rank Tests of Homogeneity Against Ordered Alternatives Based on U-Statistics.
W. Kössler
Journal of Nonparametric Statistics, 17,7 2005, 777-795Some c-Sample Rank Tests of Homogeneity Against Umbrella Alternatives with Unknown Peak.
W. Kössler
Journal of Statistical Computation and Simulation, 2005
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.Tests for Independence in Bivariate Distributions - Power Comparisons by Simulation.
W. Kössler, E. Rödel
Computational Statistics and Data Analysis 46, 2004, 645-660
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.The Efficacy of Some c-Sample Rank Tests of Homogeneity Against Ordered Alternatives.
W. Kössler, H. Büning
Journal of Nonparametric Statistics 13, 2000, 95-106The Asymptotic Power and Relative Efficiency of Some c-Sample Rank Tests of Homogeneity Against Umbrella Alternatives.
W. Kössler, H. Büning
Statistics, vol. 34, No.1, 2000, 1-26
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.
A new one-sided variable inspection plan for continuous distribution functions.
W. Kössler
Allgemeines Statistisches Archiv 83, No.4, 1999, 416-433Rank tests in the two-sample scale problem with unequal and unknown locations.
W. Kössler
Statistical Papers, vol. 40, 1999, 13-36The Asymptotic Power of Jonckheere-type tests for ordered alternatives.
W. Kössler, H. Büning
Australian & New Zealand Journal of Statistics 41, 1 1999, 67-77
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.Adaptive Tests for Umbrella Alternatives.
W. Kössler, H. Büning
Biometrical Journal, vol. 40, 5, 1998, 573-587
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.
Power of Some Tests for Umbrella Alternatives in the Multi-Sample Location Problem.
W. Kössler, H. Büning
Biometrical Journal, vol. 39, 4, 1997, 481-494On the Non-Robustness of Maximum-Likelihood Sampling Plans by Variables.
W. Kössler, H.-J. Lenz
in: H.-J.Lenz, P.Th.Wilrich (eds.): Frontiers in Statistical Quality Control 5, Physica, Heidelberg, 1997, 38-52
1996
Upper Bounds for the Complexity of Sparse and Tally Descriptions [sparse.ps.gz]
V. 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]
V. 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.Robustness and Efficiency of some Tests for ordered alternatives in the c-Sample Location Problem.
W. Kössler, H. Büning
Journal of Statistical Computation and Simulation, vol.55, 1996, 337-352A Program to Split Computer Graphics Metafiles into Individual Graphs.
W. Kössler, W. Lesener, M.Kalt
Observations, the Quarterly Technical Journal for SAS Software Users, 1996, 53-58
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]
V. 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]
V. 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.On the Robustness of Lieberman-Resnikoff Sampling Plans by Variables.
W. Kössler, H.-J. Lenz
IAPQR Transactions, Journal of the Indian Association for Productivity, Quality and Reliability, vol. 20, 93-105, 1995
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]
V. 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.ExVar - Exact Variable Inspection Plans in Statistical Quality Control.
W. Kössler, B. Lenz, H. J. Lenz
Computational Statistics & Data Analysis 17, 97-99, 1994.Restrictive adaptive tests for the treatment of the two-sample scale problem.
W. Kössler
Computational Statistics & Data Analysis 18, 513-524, 1994.
1993
Hausdorff Reductions to Sparse Sets and to Sets of High Information Content [hausdorff.ps.gz]
V. 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]
V. 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]
V. 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.
ROSTAN - a programm package using rank and order statistics.
Wolfgang Kössler
Statistical Software Newsletter, vol.15, 1989.
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öblerNonparametric Location Tests Against Restricted Alternatives.
W. Kössler
182 + xii Seiten, Shaker Verlag Aachen (2006).Nichtparametrische Lokationstests bei eingeschränkten Alternativen.
W. Kössler
Habilitationsschrift, 2003