Humboldt-Universität zu Berlin - Faculty of Mathematics and Natural Sciences - Complexity and Cryptography

Papers in Conference Proceedings

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

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

Representable Disjoint NP-Pairs [fsttcs04.pdf]
Olaf Beyersdorff
Proc. 24th Conference on Foundations of Software Technology & Theoretical Computer Science (FST&TCS), Springer-Verlag, LNCS 3328, 122-1344, 2004.

Publications in Journals

Classes of Representable Disjoint NP-Pairs
Theoretical Computer Science, Volume 377, Issues 1-3, Pages 93-109, 2007.

Tuples of Disjoint NP-Sets
To appear in the journal Theory of Computing Systems.

New Preprints

The Deduction Theorem and Complete Disjoint NP-Pairs
Technical Report, Electronic Colloquium on Computational Complexity, TR06-142.

Comparing Axiomatizations of Free Pseudospaces

A Book Contribution

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

Academic Theses

Disjoint NP-Pairs and Propositional Proof Systems
Olaf Beyersdorf
PhD thesis, Humboldt-Universität zu Berlin, 2006.

Eine stabile nicht äquationale Theorie
Olaf Beyersdorff
Diploma thesis, Humboldt-Universität zu Berlin, 2000.

Separation and Homology
Olaf Beyersdorff
Technical report, Mälardalens Högskola Västeras (Sweden), 1996.