``DNA-based parallel computation of simple arithmetic'',
[Abstract,
Paper]
Hubert Hug and Rainer Schuler
Proceedings 7th International Meeting on DNA Based Computers, LNCS, 2001, to appear.
``Strategies for the development of a peptide computer'',
[Abstract,
Paper]
Hubert Hug and Rainer Schuler
Bioinformatics 17:364--368, 2001.
``On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems'',
[Paper]
Shin Aida, Rainer Schuler, Tatsukiji, Osamu Watanabe
To appear in the Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2001.
Universal distributions and time-bounded Kolmogorov complexity
[universal-time-bounded-K.ps]
Rainer Schuler
To appear in the Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999.
On Optimal Algorithms and Optimal Proof Systems
[optalg.ps.gz]
Jochen Messner
An excerpt of a preliminary version of this paper appears in
Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, 541-550, 1999.
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 Messner
Proceedings 13th IEEE Conference on Computational Complexity (CCC), 182-185, 1998.
Resource Bounded Measure and Learnability
[measure-learning.ps.gz]
Wolfgang Lindner, Rainer Schuler and Osamu Watanabe
To appear in the Proceedings of the 13th IEEE Conference on Computational Complexity (CCC), 1998.
Optimal Proof Systems for Propositional Logic and Complete Sets
[ECCC Report,
TR97-026/Paper.ps]
Jochen Messner and Jacobo Torán
In Proceedings 15th Symposium on Theoretical Aspects of Computer Science, 1998.
On Pseudorandomness and Resource-Bounded Measure [measure.ps.gz]
Vikraman Arvind and Johannes Köbler
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]
Johannes Köbler and Wolfgang Lindner
Proceedings 8th International Workshop on Algorithmic Learning Theory (ALT'97),
Springer-Verlag, LNAI 1316, 277-290, 1997.
LR(k)
Testing is Average-Case Complete [lrktesting.ps.gz]
Christoph Karg
Proceedings 12th Conference on Computational Complexity,
1997.
A nonadaptive NC Checker for Permutation Group Intersection
V. Arvind and Jacobo Torán
Proceedings 12th Conference on Computatioanl Complexity,
1997.
A
note on universal distributions for polynomial-time computable distributions
[universal-distributions.ps.gz]
Rainer Schuler, Proc. 12th Conference on Computational Complexity,
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.
The Complexity of Generating Test Instances
[test.ps.gz]
Christoph Karg, Johannes Köbler, and Rainer Schuler
Proceedings 14th Symposium on Theoretical Aspects of Computer Science (STACS),
Springer-Verlag, LNCS 1200, 375-386, 1997.
Pattern Matching in Trace Monoids
[pm-tr.ps.gz]
Jochen Messner
Technical Report Nr. 97-01 UIB (Ulmer Informatik Berichte)
Extended Abstract in Proceedings of the 14th Symposium on Theoretical Aspects of Computer Science, 1997.
A
small span theorem within P [small-span.ps.gz]
Wolfgang Lindner and Rainer Schuler, Manuscript, 1997.
Pinpointing
Computation with Modular Queries in the Boolean Hierarchy
Manindra Agrawal, Richard Beigel, and Thomas Thierauf
Technical Report ECCC TR96-001 at http://www.eccc.uni-trier.de/eccc/, 1996.
To appear at Foundation of Software Technology and Theoretical Computer
Science (FST&TCS) 1996.
The
Boolean Isomorphism Problem
Manindra Agrawal and Thomas Thierauf
Technical Report ECCC-TR96 032.. Available at http://www.eccc.uni-trier.de/eccc/,
1996.
To appear at Symposium on Foundations of Computer Science (FOCS)
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.
On
Monotonous and Randomized Reductions to Sparse Sets [monotone.ps.gz]
Vikraman Arvind, Johannes Köbler, and Martin Mundhenk
R.A.I.R.O. Theoretical Informatics and Applications 30(2), 155-179, 1996.
The
Complexity of Generating and Checking Proofs of Membership
Harry Buhrman and Thomas Thierauf
Symposium on Theoretical Aspects of Computer Science (STACS) 96,
Springer-Verlag, LNCS 1046, 75-86, 1996.
On
the Correlation of Symmetric Functions
Jin-Yi Cai, Frederic Green, and Thomas Thierauf
Mathematical System Theory (MST) 29, 245-258, 1996.
On
the Power of Generalized MOD-Classes [mod.ps.gz]
Johannes Köbler and Seinosuke Toda
Mathematical System Theory (MST) 29, 33-46, 1996.
Truth-table
closure and Turing closure of average polynomial time have different measure
in EXP [apmeasure.ps.gz]
Rainer Schuler
In "Proceedings 11th IEEE Conference on Computational Complexity",
190-195, IEEE Computer Society, 1996.
The
Isomorphism Problem for One-Time-Only Branching Programs
Thomas Thierauf
Technical Report ECCC-TR96 040. Available at http://www.eccc.uni-trier.de/eccc/,
1996.
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.
Information
from Nonadaptive Queries to NP
Yenjo Han and Thomas Thierauf
Proceedings Structure in Complexity Theory Conference 10, 206-213,
IEEE Computer Society, 1995.
To appear in Infomation and Computation.
Nondeterministically
Selective Sets.
L. Hemaspaandra, A. Hoene, A. Naik, M Ogiwara, A. Selman, T. Thierauf,
and J. Wang
Journal on Foundations of Computer Science 6(4) , 403-416, 1995.
Structure
in Average Case Complexity [nondet-average-case-comp.ps.gz]
Christoph Karg and Rainer Schuler
In "Proceedings 6th International Symposium on Algorithms and Computation",
Lecture Notes in Computer Science 1004, 62--71, 1995
On
the Structure of Low Sets (Survey) [low.ps.gz]
Johannes Köbler
Proceedings Structure in Complexity Theory Conference 10, 246-261,
IEEE Computer Society, 1995.
New
Collapse Consequences of NP Having Small Circuits [collapse.ps.gz]
Johannes Köbler and Osamu Watanabe
International Colloquium on Automata, Languages and Programming (ICALP),
Springer-Verlag, LNCS 944, 196-207, 1995.
Average
polynomial time is hard for Exponential Time under sn-Reductions
[ap-is-sn-compl.ps.gz]
Rainer Schuler
In "Proceedings 15th Conference on the Foundations of Software Technology
and Theoretical Computer Science", Lecture Notes in Computer Science
1026, 240--247, 1995.
Some
properties of sets tractable under every polynomial-time computable distribution
[properties-of-ppcomp.ps.gz]
Rainer Schuler
Information Processing Letters (IPL) 55, 179--184. 1995
Sets
computable in polynomial time on average
[hard-sets-in-av.ps.gz]
Rainer Schuler and Tomoyuki Yamakami
In "Proceedings 1st International Conference on Computing and Combinatorics"
Lecture Notes in Computer Science 959, 400-410, 1995.
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.
On
Functions Computable with Parallel Queries to NP
Harry Buhrman, Jim Kadin, and Thomas Thierauf
Proceedings Structure in Complexity Theory 9, 43-52,
IEEE Computer Society Press, 1994.
To appear in Mathematical System Theory (MST).
Locating
P/poly Optimally in the Extended Low Hierarchy [extlow.ps.gz]
Johannes Köbler
Theoretical Computer Science (TCS) 134, 263-285, 1994.
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.
A
Note on SpanP Functions
Meena Mahajan, Thomas Thierauf, and Vinodchandran N.V.
Information Processing Letters (IPL) 51, 7-10, 1994.
On
Sets Bounded Truth-Table Reducible to P-selective Sets
Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Symposium on Theoretical Aspects of Computer Science (STACS) 94,
Springer-Verlag, LNCS 775, 427-438, 1994.
To appear in Informatique Theorique et Applications 30(2), 1996.
On
Closure Properties of GapP
Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Journal of Computational Complexity 4, 242-261, 1994.
Towards
Average-Case Complexity Analysis of NP Optimization Problems [UIB-94-13.ps.gz]
Autor: Rainer Schuler and Osamu Watanabe
In "Proceedings 10th Annual Conference on Structure in Complexity
Theory", IEEE Computer Society Press, 148--159, 1995.
Structural
Average Case Complexity [structural-average-case.ps.gz]
Autor: Rainer Schuler and Tomoyuki Yamakami
Journal of Computer and System Sciences, (JCSS) 52(2) 308--327,
1996.
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
Recent Developments in Complexity Theory, Cambridge University Press,
1993.
(Here you find the full version which is University of Rochester TR 417,
1992.)
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.
Threshold
Computation and Cryptographic Security
Yenjo Han, Lane A. Hemaspaandraanda, and Thomas Thierauf
Proceedings 4th International Symposium Algorithms and Computation (ISAAC)
93, 230-239,
Springer-Verlag, LNCS 762, 1993.
To appear in SIAM Journal on Computing.
On
Closure Properties of #P in the Context of PF(#P)
Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Proceedings Structure in Complexity Theory Conference 8, 139-146,
IEEE Computer Society, 1993.
To appear in Journal of Computer and System Sciences (JCSS).
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.
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.
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.
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.
Random
languages for nonuniform complexity classes [random-languages.ps.gz]
Autor: Martin Mundhenk and Rainer Schuler
Journal of Complexity, 7 296--310, 1991.