Olaf Beyersdorff

176 papers A* 8A 31B 3C 8Misc 3Journal 107Unranked 13
YearRankTypeTitle / Venue / Authors
2026 A* conf
Proof Systems That Tightly Characterise Model Counting Algorithms.
AAAI
Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche
2026 A* conf
Proof Systems for Tensor-based Model Counting.
AAAI
Olaf Beyersdorff, Joachim Giesen, Andreas Goral, Tim Hoffmann, Kaspar Kasche, Christoph Staudt
2025 A ed.
42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, Jena, Germany, March 4-7, 2025
STACS
Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, Kim Thang Nguyen
2025 A* conf
Computationally Hard Problems Are Hard for QBF Proof Systems Too.
AAAI
Agnes Schleitzer, Olaf Beyersdorff
2025 J jnl
Proof Systems That Tightly Characterise Model Counting Algorithms.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche
2025 J jnl
Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs.
J. Autom. Reason.
Olaf Beyersdorff, Benjamin Böhm, Meena Mahajan
2025 A conf
Semi-Algebraic Proof Systems for QBF.
SAT
Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann
2025 J jnl
Semi-Algebraic Proof Systems for QBF.
CoRR
Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann
2024 A ed.
41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, Clermont-Ferrand, France, March 12-14, 2024
STACS
Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, Daniel Lokshtanov
2024 J jnl
Computationally Hard Problems Are Hard for QBF Proof Systems Too.
Electron. Colloquium Comput. Complex.
Agnes Schleitzer, Olaf Beyersdorff
2024 J jnl
Hard QBFs for Merge Resolution.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2024 B conf
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds Through Circuits and Degree.
MFCS
Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche, Luc Nicolas Spachmann
2024 J jnl
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann
2024 J jnl
Proof Complexity of Propositional Model Counting.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann
2024 J jnl
Proof Complexity of Propositional Model Counting.
J. Satisf. Boolean Model. Comput.
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann
2024 J jnl
QCDCL vs QBF Resolution: Further Insights.
J. Artif. Intell. Res.
Benjamin Böhm, Olaf Beyersdorff
2024 J jnl
QCDCL with cube learning or pure literal elimination - What is best?
Artif. Intell.
Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff
2024 A* conf
Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs.
AAAI
Olaf Beyersdorff, Benjamin Böhm, Meena Mahajan
2024 J jnl
SAT and Interactions (Dagstuhl Seminar 24421).
Dagstuhl Reports
Olaf Beyersdorff, Laura Kovács, Meena Mahajan, Martina Seidl, Kaspar Kasche
2024 J jnl
Should Decisions in QCDCL Follow Prefix Order?
J. Autom. Reason.
Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff
2024 J jnl
Strong (D)QBF Dependency Schemes via Implication-free Resolution Paths.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Joshua Lewis Blinkhorn, Tomás Peitl
2024 A conf
The Relative Strength of #SAT Proof Systems.
SAT
Olaf Beyersdorff, Johannes Klaus Fichte, Markus Hecher, Tim Hoffmann, Kaspar Kasche
2024 J jnl
The Riis Complexity Gap for QBF Resolution.
J. Satisf. Boolean Model. Comput.
Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
2023 J jnl
Classes of Hard Formulas for QBF Resolution.
J. Artif. Intell. Res.
Agnes Schleitzer, Olaf Beyersdorff
2023 J jnl
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution.
ACM Trans. Comput. Log.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl
2023 J jnl
Lower Bounds for QCDCL via Formula Gauge.
J. Autom. Reason.
Benjamin Böhm, Olaf Beyersdorff
2023 A conf
Proof Complexity of Propositional Model Counting.
SAT
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann
2023 A conf
QCDCL vs QBF Resolution: Further Insights.
SAT
Benjamin Böhm, Olaf Beyersdorff
2023 J jnl
QCDCL vs QBF Resolution: Further Insights.
Electron. Colloquium Comput. Complex.
Benjamin Böhm, Olaf Beyersdorff
2023 J jnl
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution.
Log. Methods Comput. Sci.
Olaf Beyersdorff, Benjamin Böhm
2022 A conf
Classes of Hard Formulas for QBF Resolution.
SAT
Agnes Schleitzer, Olaf Beyersdorff
2022 J jnl
Classes of Hard Formulas for QBF Resolution.
Electron. Colloquium Comput. Complex.
Agnes Schleitzer, Olaf Beyersdorff
2022 J jnl
Proof Complexity of Modal Resolution.
J. Autom. Reason.
Sarah Sigley, Olaf Beyersdorff
2022 A* conf
QCDCL with Cube Learning or Pure Literal Elimination - What is Best?
IJCAI
Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff
2022 A conf
Should Decisions in QCDCL Follow Prefix Order?
SAT
Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff
2022 J jnl
Should decisions in QCDCL follow prefix order?
Electron. Colloquium Comput. Complex.
Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff
2022 J jnl
Theory and Practice of SAT and Combinatorial Solving (Dagstuhl Seminar 22411).
Dagstuhl Reports
Olaf Beyersdorff, Armin Biere, Vijay Ganesh, Jakob Nordström, Andy Oertel
2021 J jnl
A simple proof of QBF hardness.
Inf. Process. Lett.
Olaf Beyersdorff, Joshua Blinkhorn
2021 J jnl
Building Strategies into QBF Proofs.
J. Autom. Reason.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2021 A conf
Lower Bounds for QCDCL via Formula Gauge.
SAT
Benjamin Böhm, Olaf Beyersdorff
2021 A conf
QBFFam: A Tool for Generating QBF Families from Proof Complexity.
SAT
Olaf Beyersdorff, Luca Pulina, Martina Seidl, Ankit Shukla
2021 J jnl
QCDCL with Cube Learning or Pure Literal Elimination - What is best?
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Benjamin Böhm
2021 — ch.
Quantified Boolean Formulas.
Handbook of Satisfiability
Olaf Beyersdorff, Mikolás Janota, Florian Lonsing, Martina Seidl
2021 J jnl
Strong (D)QBF Dependency Schemes via Implication-free Resolution Paths.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Tomás Peitl
2021 A conf
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution.
ITCS
Olaf Beyersdorff, Benjamin Böhm
2021 J jnl
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution.
CoRR
Olaf Beyersdorff, Benjamin Böhm
2020 J jnl
Dynamic QBF Dependencies in Reduction and Expansion.
ACM Trans. Comput. Log.
Olaf Beyersdorff, Joshua Blinkhorn
2020 J jnl
Frege Systems for Quantified Boolean Logic.
J. ACM
Olaf Beyersdorff, Ilario Bonacina, Leroy Chew, Ján Pich
2020 — conf
Hard QBFs for Merge Resolution.
FSTTCS
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2020 J jnl
Hard QBFs for Merge Resolution.
CoRR
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2020 J jnl
Hard QBFs for Merge Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2020 A* conf
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution.
LICS
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2020 J jnl
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2020 J jnl
Lower Bound Techniques for QBF Expansion.
Theory Comput. Syst.
Olaf Beyersdorff, Joshua Blinkhorn
2020 J jnl
Reasons for Hardness in QBF Proof Systems.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Luke Hinde, Ján Pich
2020 J jnl
SAT and Interactions (Dagstuhl Seminar 20061).
Dagstuhl Reports
Olaf Beyersdorff, Uwe Egly, Meena Mahajan, Cláudia Nalon
2020 A conf
Strong (D)QBF Dependency Schemes via Tautology-Free Resolution Paths.
SAT
Olaf Beyersdorff, Joshua Blinkhorn, Tomás Peitl
2020 J jnl
Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Tomás Peitl
2020 J jnl
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Benjamin Böhm
2019 J jnl
A game characterisation of tree-like Q-Resolution size.
J. Comput. Syst. Sci.
Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah
2019 A conf
Building Strategies into QBF Proofs.
STACS
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2019 J jnl
Characterising tree-like Frege proofs for QBF.
Inf. Comput.
Olaf Beyersdorff, Luke Hinde
2019 J jnl
New Resolution-Based QBF Calculi and Their Proof Complexity.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Leroy Chew, Mikolás Janota
2019 A conf
Proof Complexity of QBF Symmetry Recomputation.
SAT
Joshua Blinkhorn, Olaf Beyersdorff
2019 J jnl
Proof Complexity of Symmetry Learning in QBF.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn
2019 J jnl
Reinterpreting Dependency Schemes: Soundness Meets Incompleteness in DQBF.
J. Autom. Reason.
Olaf Beyersdorff, Joshua Blinkhorn, Leroy Chew, Renate A. Schmidt, Martin Suda
2019 A conf
Short Proofs in QBF Expansion.
SAT
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan
2019 J jnl
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs.
Log. Methods Comput. Sci.
Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde
2018 J jnl
Are Short Proofs Narrow? QBF Resolution Is
ACM Trans. Comput. Log.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2018 J jnl
Building Strategies into QBF Proofs.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2018 A* conf
Dynamic Dependency Awareness for QBF.
IJCAI
Joshua Blinkhorn, Olaf Beyersdorff
2018 A conf
Genuine Lower Bounds for QBF Expansion.
STACS
Olaf Beyersdorff, Joshua Blinkhorn
2018 J jnl
More on Size and Width in QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Judith Clymo
2018 J jnl
Relating size and width in variants of Q-resolution.
Inf. Process. Lett.
Judith Clymo, Olaf Beyersdorff
2018 J jnl
Short Proofs in QBF Expansion.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan
2018 A conf
Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs.
ITCS
Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde
2018 J jnl
The Riis Complexity Gap for QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
2018 A ed.
Theory and Applications of Satisfiability Testing - SAT 2018 - 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9-12, 2018, Proceedings
SAT
Olaf Beyersdorff, Christoph M. Wintersteiger
2018 J jnl
Understanding cutting planes for QBFs.
Inf. Comput.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2017 J jnl
Feasible Interpolation for QBF Resolution Calculi.
Log. Methods Comput. Sci.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2017 J jnl
Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn
2017 — conf
Reasons for Hardness in QBF Proof Systems.
FSTTCS
Olaf Beyersdorff, Luke Hinde, Ján Pich
2017 J jnl
Reasons for Hardness in QBF Proof Systems.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Luke Hinde, Ján Pich
2017 A conf
Shortening QBF Proofs with Dependency Schemes.
SAT
Joshua Blinkhorn, Olaf Beyersdorff
2017 J jnl
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs.
CoRR
Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde
2017 J jnl
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde
2017 J jnl
Understanding Cutting Planes for QBFs.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 A conf
Are Short Proofs Narrow? QBF Resolution is not Simple.
STACS
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 A conf
Dependency Schemes in QBF Calculi: Semantics and Soundness.
CP
Olaf Beyersdorff, Joshua Blinkhorn
2016 — conf
Dependency Schemes in QBF Calculi: Semantics and Soundness.
QBF@SAT
Joshua Blinkhorn, Olaf Beyersdorff
2016 J jnl
Dependency Schemes in QBF Calculi: Semantics and Soundness.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn
2016 — conf
Extension Variables in QBF Resolution.
AAAI Workshop: Beyond NP
Olaf Beyersdorff, Leroy Chew, Mikolas Janota
2016 J jnl
Extension Variables in QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Mikolas Janota
2016 J jnl
Feasible Interpolation for QBF Resolution Calculi.
CoRR
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 A conf
Lifting QBF Resolution Calculi to DQBF.
SAT
Olaf Beyersdorff, Leroy Chew, Renate A. Schmidt, Martin Suda
2016 J jnl
Lifting QBF Resolution Calculi to DQBF.
CoRR
Olaf Beyersdorff, Leroy Chew, Renate A. Schmidt, Martin Suda
2016 J jnl
Lifting QBF Resolution Calculi to DQBF.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Renate A. Schmidt, Martin Suda
2016 A conf
Lower Bounds: From Circuits to QBF Proof Systems.
ITCS
Olaf Beyersdorff, Ilario Bonacina, Leroy Chew
2016 J jnl
SAT and Interactions (Dagstuhl Seminar 16381).
Dagstuhl Reports
Olaf Beyersdorff, Nadia Creignou, Uwe Egly, Heribert Vollmer
2016 — conf
Understanding Cutting Planes for QBFs.
FSTTCS
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 A* conf
Understanding Gentzen and Frege Systems for QBF.
LICS
Olaf Beyersdorff, Ján Pich
2016 J jnl
Understanding Gentzen and Frege systems for QBF.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Ján Pich
2015 C conf
A Game Characterisation of Tree-like Q-resolution Size.
LATA
Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah
2015 J jnl
Are Short Proofs Narrow? QBF Resolution is not Simple.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2015 — conf
Feasible Interpolation for QBF Resolution Calculi.
ICALP (1)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2015 J jnl
Feasible Interpolation for QBF Resolution Calculi.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2015 J jnl
Lower bounds: from circuits to QBF proof systems.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Ilario Bonacina, Leroy Chew
2015 A conf
Proof Complexity of Resolution-based QBF Calculi.
STACS
Olaf Beyersdorff, Leroy Chew, Mikolás Janota
2014 J jnl
A game characterisation of tree-like Q-Resolution size.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah
2014 — conf
On Unification of QBF Resolution-Based Calculi.
MFCS (2)
Olaf Beyersdorff, Leroy Chew, Mikolas Janota
2014 J jnl
On Unification of QBF Resolution-Based Calculi.
Electron. Colloquium Comput. Complex.
Mikolas Janota, Leroy Chew, Olaf Beyersdorff
2014 J jnl
Optimal algorithms and proofs (Dagstuhl Seminar 14421).
Dagstuhl Reports
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam
2014 J jnl
Proof Complexity of Resolution-based QBF Calculi.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Mikolas Janota
2014 J jnl
Tableau vs. Sequent Calculi for Minimal Entailment.
CoRR
Olaf Beyersdorff, Leroy Chew
2014 J jnl
Tableau vs. Sequent Calculi for Minimal Entailment.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew
2014 A conf
The Complexity of Theorem Proving in Circumscription and Minimal Entailment.
IJCAR
Olaf Beyersdorff, Leroy Chew
2014 J jnl
The Complexity of Theorem Proving in Circumscription and Minimal Entailment.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew
2014 A conf
Unified Characterisations of Resolution Hardness Measures.
SAT
Olaf Beyersdorff, Oliver Kullmann
2013 J jnl
A characterization of tree-like Resolution size.
Inf. Process. Lett.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2013 J jnl
Parameterized Complexity of DPLL Search Procedures.
ACM Trans. Comput. Log.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2013 A conf
The Complexity of Theorem Proving in Autoepistemic Logic.
SAT
Olaf Beyersdorff
2013 J jnl
The Complexity of Theorem Proving in Autoepistemic Logic.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff
2013 J jnl
Verifying proofs in constant depth.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2012 J jnl
A Characterization of Tree-Like Resolution Size.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2012 — book
Non-classical Aspects in Proof Complexity.
Olaf Beyersdorff
2012 J jnl
Parameterized Bounded-Depth Frege Is not Optimal.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2012 J jnl
The complexity of reasoning for fragments of default logic.
J. Log. Comput.
Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer
2012 J jnl
Verifying Proofs in Constant Depth.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2011 J jnl
Do there exist complete sets for promise classes?
Math. Log. Q.
Olaf Beyersdorff, Zenon Sadowski
2011 J jnl
Model Checking CTL is Almost Always Inherently Sequential
Log. Methods Comput. Sci.
Olaf Beyersdorff, Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Heribert Vollmer
2011 — conf
Parameterized Bounded-Depth Frege Is Not Optimal.
ICALP (1)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2011 A conf
Parameterized Complexity of DPLL Search Procedures.
SAT
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2011 — conf
Proof Complexity of Non-classical Logics.
ESSLLI
Olaf Beyersdorff, Oliver Kutz
2011 J jnl
Proof complexity of propositional default logic.
Arch. Math. Log.
Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, Heribert Vollmer
2011 J jnl
Proof systems that take advice.
Inf. Comput.
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2011 B conf
Verifying Proofs in Constant Depth.
MFCS
Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2010 J jnl
A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games.
Inf. Process. Lett.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
A tight Karp-Lipton collapse result in bounded arithmetic.
ACM Trans. Comput. Log.
Olaf Beyersdorff, Sebastian Müller
2010 C conf
Different Approaches to Proof Systems.
TAMC
Olaf Beyersdorff, Sebastian Müller
2010 — conf
Hardness of Parameterized Resolution.
Circuits, Logic, and Games
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
Hardness of Parameterized Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
2010 J jnl
Parameterized Bounded-Depth Frege is Not Optimal.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2010 C conf
Proof Complexity of Non-classical Logics.
TAMC
Olaf Beyersdorff
2010 — conf
Proof Complexity of Propositional Default Logic.
Circuits, Logic, and Games
Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, Heribert Vollmer
2010 A conf
Proof Complexity of Propositional Default Logic.
SAT
Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, Heribert Vollmer
2010 J jnl
The Deduction Theorem for Strong Propositional Proof Systems.
Theory Comput. Syst.
Olaf Beyersdorff
2009 Misc conf
Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes.
CSR
Olaf Beyersdorff, Zenon Sadowski
2009 J jnl
Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Zenon Sadowski
2009 J jnl
Comparing axiomatizations of free pseudospaces.
Arch. Math. Log.
Olaf Beyersdorff
2009 A conf
Does Advice Help to Prove Propositional Tautologies?
SAT
Olaf Beyersdorff, Sebastian Müller
2009 C conf
Edges as Nodes - a New Approach to Timetable Information .
ATMOS
Olaf Beyersdorff, Yevgen Nebesov
2009 C conf
Model Checking CTL is Almost Always Inherently Sequential.
TIME
Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer, Martin Mundhenk, Thomas Schneider
2009 C conf
Nondeterministic Instance Complexity and Proof Systems with Advice.
LATA
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2009 J jnl
Nondeterministic functions and the existence of optimal proof systems.
Theor. Comput. Sci.
Olaf Beyersdorff, Johannes Köbler, Jochen Messner
2009 Misc conf
On the Existence of Complete Disjoint NP-Pairs.
SYNASC
Olaf Beyersdorff
2009 J jnl
On the correspondence between arithmetic theories and propositional proof systems - a survey.
Math. Log. Q.
Olaf Beyersdorff
2009 J jnl
Proof Systems that Take Advice.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2009 A conf
The Complexity of Reasoning for Fragments of Default Logic.
SAT
Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer
2009 J jnl
The complexity of propositional implication.
Inf. Process. Lett.
Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer
2008 B conf
A Tight Karp-Lipton Collapse Result in Bounded Arithmetic.
CSL
Olaf Beyersdorff, Sebastian Müller
2008 C conf
Logical Closure Properties of Propositional Proof Systems.
TAMC
Olaf Beyersdorff
2008 J jnl
Nondeterministic Instance Complexity and Proof Systems with Advice.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
2008 J jnl
The Complexity of Propositional Implication
CoRR
Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer
2008 J jnl
The Complexity of Reasoning for Fragments of Default Logic
CoRR
Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer
2008 J jnl
Tuples of Disjoint NP-Sets.
Theory Comput. Syst.
Olaf Beyersdorff
2007 J jnl
Classes of representable disjoint NP-pairs.
Theor. Comput. Sci.
Olaf Beyersdorff
2007 — conf
The Deduction Theorem for Strong Propositional Proof Systems.
FSTTCS
Olaf Beyersdorff
2006 C conf
Disjoint NP-Pairs from Propositional Proof Systems.
TAMC
Olaf Beyersdorff
2006 — —
Disjoint NP-pairs and propositional proof systems.
Olaf Beyersdorff
2006 J jnl
On the Deduction Theorem and Complete Disjoint NP-Pairs.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff
2006 Misc conf
Tuples of Disjoint NP-Sets.
CSR
Olaf Beyersdorff
2005 J jnl
Disjoint NP-Pairs from Propositional Proof Systems
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff
2005 J jnl
Tuples of Disjoint NP-Sets
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff
2004 J jnl
Representable Disjoint NP-Pairs
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff
2004 — conf
Representable Disjoint NP-Pairs.
FSTTCS
Olaf Beyersdorff