Olaf Beyersdorff

Olaf Beyersdorff: The Complexity of Theorem Proving in Autoepistemic Logic. Electronic Colloquium on Computational Complexity (ECCC) 20: 16 (2013)

Olaf Beyersdorff: Non-classical Aspects in Proof Complexity. Cuvillier 2012, isbn 978-3-9540403-6-0, pp. I-XI, 1-124

Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer: The complexity of reasoning for fragments of default logic. J. Log. Comput. 22(3): 587-604 (2012)

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege Is not Optimal. TOCT 4(3): 7 (2012)

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer: Verifying Proofs in Constant Depth. Electronic Colloquium on Computational Complexity (ECCC) 19: 79 (2012)

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria: A Characterization of Tree-Like Resolution Size. Electronic Colloquium on Computational Complexity (ECCC) 19: 161 (2012)

Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, Heribert Vollmer: Proof complexity of propositional default logic. Arch. Math. Log. 50(7-8): 727-742 (2011)

Olaf Beyersdorff, Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Heribert Vollmer: Model Checking CTL is Almost Always Inherently Sequential. Logical Methods in Computer Science 7(2) (2011)

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller: Proof systems that take advice. Inf. Comput. 209(3): 320-332 (2011)

Olaf Beyersdorff, Zenon Sadowski: Do there exist complete sets for promise classes? Math. Log. Q. 57(6): 535-550 (2011)

Olaf Beyersdorff, Oliver Kutz: Proof Complexity of Non-classical Logics. ESSLLI 2011: 1-54

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) 2011: 630-641

Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer: Verifying Proofs in Constant Depth. MFCS 2011: 84-95

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria: Parameterized Complexity of DPLL Search Procedures. SAT 2011: 5-18

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria: A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games. Inf. Process. Lett. 110(23): 1074-1077 (2010)

Olaf Beyersdorff: The Deduction Theorem for Strong Propositional Proof Systems. Theory Comput. Syst. 47(1): 162-178 (2010)

Olaf Beyersdorff, Sebastian Müller: A tight Karp-Lipton collapse result in bounded arithmetic. ACM Trans. Comput. Log. 11(4) (2010)

Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, Heribert Vollmer: Proof Complexity of Propositional Default Logic. SAT 2010: 30-43

Olaf Beyersdorff: Proof Complexity of Non-classical Logics. TAMC 2010: 15-27

Olaf Beyersdorff, Sebastian Müller: Different Approaches to Proof Systems. TAMC 2010: 50-59

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria: Hardness of Parameterized Resolution. Electronic Colloquium on Computational Complexity (ECCC) 17: 59 (2010)

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria: A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games. Electronic Colloquium on Computational Complexity (ECCC) 17: 81 (2010)

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege is Not Optimal. Electronic Colloquium on Computational Complexity (ECCC) 17: 198 (2010)

Olaf Beyersdorff: Comparing axiomatizations of free pseudospaces. Arch. Math. Log. 48(7): 625-641 (2009)

Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer: The complexity of propositional implication. Inf. Process. Lett. 109(18): 1071-1077 (2009)

Olaf Beyersdorff: On the correspondence between arithmetic theories and propositional proof systems - a survey. Math. Log. Q. 55(2): 116-137 (2009)

Olaf Beyersdorff, Johannes Köbler, Jochen Messner: Nondeterministic functions and the existence of optimal proof systems. Theor. Comput. Sci. 410(38-40): 3839-3855 (2009)

Olaf Beyersdorff, Yevgen Nebesov: Edges as Nodes - a New Approach to Timetable Information . ATMOS 2009

Olaf Beyersdorff, Zenon Sadowski: Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes. CSR 2009: 47-58

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller: Nondeterministic Instance Complexity and Proof Systems with Advice. LATA 2009: 164-175

Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer: The Complexity of Reasoning for Fragments of Default Logic. SAT 2009: 51-64

Olaf Beyersdorff, Sebastian Müller: Does Advice Help to Prove Propositional Tautologies? SAT 2009: 65-72

Olaf Beyersdorff: On the Existence of Complete Disjoint NP-Pairs. SYNASC 2009: 282-289

Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer, Martin Mundhenk, Thomas Schneider: Model Checking CTL is Almost Always Inherently Sequential. TIME 2009: 21-28

Olaf Beyersdorff, Zenon Sadowski: Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes. Electronic Colloquium on Computational Complexity (ECCC) 16: 81 (2009)

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller: Proof Systems that Take Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 92 (2009)

Olaf Beyersdorff: Tuples of Disjoint NP-Sets. Theory Comput. Syst. 43(2): 118-135 (2008)

Olaf Beyersdorff, Sebastian Müller: A Tight Karp-Lipton Collapse Result in Bounded Arithmetic. CSL 2008: 199-214

Olaf Beyersdorff: Logical Closure Properties of Propositional Proof Systems. TAMC 2008: 318-329

Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer: The Complexity of Reasoning for Fragments of Default Logic. CoRR abs/0808.3884 (2008)

Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer: The Complexity of Propositional Implication. CoRR abs/0811.0959 (2008)

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller: Nondeterministic Instance Complexity and Proof Systems with Advice. Electronic Colloquium on Computational Complexity (ECCC) 15(075) (2008)

Olaf Beyersdorff: Classes of representable disjoint NP-pairs. Theor. Comput. Sci. 377(1-3): 93-109 (2007)

Olaf Beyersdorff: The Deduction Theorem for Strong Propositional Proof Systems. FSTTCS 2007: 241-252

Olaf Beyersdorff: Disjoint NP-pairs and propositional proof systems. Humboldt University of Berlin 2006

Olaf Beyersdorff: Tuples of Disjoint NP-Sets. CSR 2006: 80-91

Olaf Beyersdorff: Disjoint NP-Pairs from Propositional Proof Systems. TAMC 2006: 236-247

Olaf Beyersdorff: On the Deduction Theorem and Complete Disjoint NP-Pairs. Electronic Colloquium on Computational Complexity (ECCC) 13(142) (2006)

Olaf Beyersdorff: Disjoint NP-Pairs from Propositional Proof Systems. Electronic Colloquium on Computational Complexity (ECCC)(083) (2005)

Olaf Beyersdorff: Tuples of Disjoint NP-Sets. Electronic Colloquium on Computational Complexity (ECCC)(123) (2005)

Olaf Beyersdorff: Representable Disjoint NP-Pairs. FSTTCS 2004: 122-134

Olaf Beyersdorff: Representable Disjoint NP-Pairs. Electronic Colloquium on Computational Complexity (ECCC)(082) (2004)