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

Publications of Olaf Beyersdorff

2010

Proof Complexity of Propositional Default Logic
With Arne Meier, Sebastian Müller, Michael Thomas and Heribert Vollmer,
Preprint, submitted.

The Strength of Parameterized Tree-like Resolution
With Nicola Galesi and Massimo Lauria
Preprint, submitted.

2009

Proof Systems that Take Advice
With Johannes Köbler and Sebastian Müller
Submitted for publication.

On the Existence of Complete Disjoint NP-Pairs
Proc. 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), IEEE Computer Society Press, To appear.

Edges as Nodes - a New Approach to Timetable Information
with Yevgen Nebesov
Proc. 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), Dagstuhl Research Online Publication Server (DROPS), To appear.

The Complexity of Propositional Implication
With Arne Meier, Michael Thomas and Heribert Vollmer,
Information Processing Letters, Volume 109, Number 18, Pages 1071 - 1077, 2009.

A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
With Sebastian Müller
ACM Transactions on Computational Logic.
To appear.

Nondeterministic Functions and the Existence of Optimal Proof Systems
With Johannes Köbler and Jochen Messner
Theoretical Computer Science, Volume 410, Number 38 - 40, Pages 3839 - 3855, 2009.

The Deduction Theorem for Strong Propositional Proof Systems
Theory of Computing Systems, To appear.

Comparing Axiomatizations of Free Pseudospaces
Archive for Mathematical Logic. Volume 48, Number 7, Pages 625 - 641, 2009.

Model Checking CTL is Almost Always Inherently Sequential
With Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas and Heribert Vollmer
Proc. 16th International Symposium on Temporal Representation and Reasoning (TIME), IEEE Computer Society Press, Pages 21 - 28, 2009.

Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
With Zenon Sadowski
Proc. 4th Computer Science Symposium in Russia (CSR), Springer-Verlag, LNCS 5675, Pages 47 - 58, 2009.

The Complexity of Reasoning for Fragments of Default Logic
With Arne Meier, Michael Thomas and Heribert Vollmer
Proc. 12th International Conference on Theory and Applications of Satisfiability Testing (SAT), Springer-Verlag, LNCS 5584, Pages 51 - 64, 2009.

Does Advice Help to Prove Propositional Tautologies?
With Sebastian Müller
Proc. 12th International Conference on Theory and Applications of Satisfiability Testing (SAT), Springer-Verlag, LNCS 5584, Pages 65 - 72, 2009.

Nondeterministic Instance Complexity and Proof Systems with Advice
With Johannes Köbler and Sebastian Müller
Proc. 3rd International Conference on Language and Automata Theory and Applications (LATA), Springer-Verlag, LNCS 5457, Pages 164 - 175, 2009.

On the Correspondence Between Arithmetic Theories and Propositional Proof Systems - a Survey
Mathematical Logic Quarterly, Volume 55, Number 2, Pages 116 - 137, 2009.

2008

A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
(Extended Abstract)
With Sebastian Müller
Proc. 17th EACSL Annual Conference on Computer Science Logic (CSL),
Springer-Verlag, LNCS 5213, Pages 199-214, 2008.

Nondeterministic Functions and the Existence of Optimal Proof Systems
With Johannes Köbler and Jochen Messner
Submitted for publication.

Comparing Axiomatizations of Free Pseudospaces
Submitted for publication.

On the Correspondence Between Arithmetic Theories and Propositional Proof Systems - a Survey
Mathematical Logic Quarterly, To appear.

Tuples of Disjoint NP-Sets
Theory of Computing Systems, To appear.

Logical Closure Properties of Propositional Proof Systems
(Extended Abstract)
Proc. 5th Annual Conference on Theory and Applications of Models of Computation (TAMC)
, LNCS 4978, Pages 318-329, 2008.

2007

The Deduction Theorem for Strong Propositional Proof Systems
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
Theoretical Computer Science, Volume 377, Issues 1-3, Pages 93-109, 2007.

2006

Disjoint NP-Pairs from propositional proof systems
(Extended Abstract)
Proc. 3rd Conference on Theory and Applications of Models of Computation (TAMC), Springer Verlag, LNCS 3959, 236-247, 2006.

Tuples of Disjoint NP-Sets
(Extended Abstract)
Proc. 1st International Computer Science Symposium in Russia (CSR), Springer Verlag, LNCS 3967, 80-91, 2006.

Disjoint NP-Pairs and Propositional Proof Systems
Dissertation, Humboldt-Universität zu Berlin, 2006.

Von der Turingmaschine zum Quantencomputer
(Zusammen mit Johannes Köbler)
Themen der Informatik im historischen Kontext
, Springer Verlag, 2006.

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

2005

Tuples of Disjoint NP-Sets
Technical Report, Electronic Colloquium on Computational Complexity, TR05-123.

Disjoint NP-Pairs from propositional proof systems
Technical Report, Electronic Colloquium on Computational Complexity, TR05-83.

2004

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

Representable Disjoint NP-Pairs
(Extended version of the above conference paper)
Technical Report, Electronic Colloquium on Computational Complexity, TR04-082.

2000

Eine stabile nicht äquationale Theorie
Diploma thesis (Diplomarbeit), Humboldt-Universität zu Berlin, 2000.

1996

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