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

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, 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.

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, Duesseldorf

Some c-Sample Rank Tests of Homogeneity Against Ordered Alternatives Based on U-Statistics.
W. Kössler
Journal of Nonparametric Statistics, 17,7 2005, 777-795

Some 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-106

The 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-433

Rank tests in the two-sample scale problem with unequal and unknown locations.
W. Kössler
Statistical Papers, vol. 40, 1999, 13-36

The 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-494

On 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-352

A 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öbler

Nonparametric 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