×

zbMATH — the first resource for mathematics

Beyersdorff, Olaf

Compute Distance To:
Author ID: beyersdorff.olaf Recent zbMATH articles by "Beyersdorff, Olaf"
Published as: Beyersdorff, Olaf
External Links: MGP · ORCID · dblp
Documents Indexed: 69 Publications since 2004, including 2 Books
Reviewing Activity: 2 Reviews

Publications by Year

Citations contained in zbMATH Open

52 Publications have been cited 199 times in 76 Documents Cited by Year
Proof complexity of resolution-based QBF calculi. Zbl 1355.68105
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
21
2015
On unification of QBF resolution-based calculi. Zbl 1426.68283
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
19
2014
A characterization of tree-like resolution size. Zbl 1285.68058
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
10
2013
Lower bounds: from circuits to QBF proof systems. Zbl 1334.68084
Beyersdorff, Olaf; Bonacina, Ilario; Leroy, Chew
9
2016
The complexity of propositional implication. Zbl 1202.68207
Beyersdorff, Olaf; Meier, Arne; Thomas, Michael; Vollmer, Heribert
8
2009
Classes of representable disjoint NP-pairs. Zbl 1118.68069
Beyersdorff, Olaf
8
2007
Nondeterministic functions and the existence of optimal proof systems. Zbl 1171.68010
Beyersdorff, Olaf; Köbler, Johannes; Messner, Jochen
7
2009
Understanding Gentzen and Frege systems for QBF. Zbl 1395.03028
Beyersdorff, Olaf; Pich, Ján
6
2016
A game characterisation of tree-like Q-resolution size. Zbl 1425.03027
Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek
6
2015
Parameterized complexity of DPLL search procedures. Zbl 1354.68105
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
6
2013
A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games. Zbl 1379.03017
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
6
2010
Feasible interpolation for QBF resolution calculi. Zbl 1440.68320
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
5
2015
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
5
2012
Parameterized complexity of DPLL search procedures. Zbl 1330.68099
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
5
2011
Model checking CTL is almost always inherently sequential. Zbl 1220.68068
Beyersdorff, Olaf; Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Vollmer, Heribert
5
2011
Size, cost, and capacity: a semantic technique for hard random qbfs. Zbl 07029312
Beyersdorff, Olaf; Blinkhorn, Joshua; Hinde, Luke
4
2019
Are short proofs narrow? QBF resolution is not so simple. Zbl 1407.03072
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
4
2018
Feasible interpolation for QBF resolution calculi. Zbl 1448.68456
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
4
2017
The complexity of reasoning for fragments of default logic. Zbl 1247.68263
Beyersdorff, Olaf; Meier, Arne; Thomas, Michael; Vollmer, Heribert
4
2009
Tuples of disjoint \(\mathsf{NP}\)-sets. Zbl 1148.68021
Beyersdorff, Olaf
4
2008
Unified characterisations of resolution hardness measures. Zbl 1423.68409
Beyersdorff, Olaf; Kullmann, Oliver
3
2014
The complexity of reasoning for fragments of default logic. Zbl 1267.68222
Beyersdorff, Olaf; Meier, Arne; Thomas, Michael; Vollmer, Heribert
3
2012
On the correspondence between arithmetic theories and propositional proof systems – a survey. Zbl 1168.03042
Beyersdorff, Olaf
3
2009
Nondeterministic instance complexity and proof systems with advice. Zbl 1234.03035
Beyersdorff, Olaf; Köbler, Johannes; Müller, Sebastian
3
2009
A tight Karp-Lipton collapse result in bounded arithmetic. Zbl 1157.03032
Beyersdorff, Olaf; Müller, Sebastian
3
2008
The deduction theorem for strong propositional proof systems. (Extended abstract). Zbl 1135.03347
Beyersdorff, Olaf
3
2007
Understanding cutting planes for QBFs. Zbl 06944937
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
2
2018
Shortening QBF proofs with dependency schemes. Zbl 06807231
Blinkhorn, Joshua; Beyersdorff, Olaf
2
2017
Understanding cutting planes for QBFs. Zbl 1391.03041
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
2
2016
Are short proofs narrow? QBF resolution is not simple. Zbl 1388.03053
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
2
2016
Do there exist complete sets for promise classes? Zbl 1253.68138
Beyersdorff, Olaf; Sadowski, Zenon
2
2011
Proof complexity of propositional default logic. Zbl 1308.03057
Beyersdorff, Olaf; Meier, Arne; Müller, Sebastian; Thomas, Michael; Vollmer, Heribert
2
2011
Parameterized bounded-depth Frege is not optimal. Zbl 1334.03056
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander
2
2011
A tight Karp-Lipton collapse result in bounded arithmetic. Zbl 1351.03055
Beyersdorff, Olaf; Müller, Sebastian
2
2010
Logical closure properties of propositional proof systems. (Extended abstract). Zbl 1139.03316
Beyersdorff, Olaf
2
2008
Hardness characterisations and size-width lower bounds for QBF resolution. Zbl 07299470
Beyersdorff, Olaf; Blinkhorn, Joshua; Mahajan, Meena
1
2020
Frege systems for quantified Boolean logic. Zbl 07273080
Beyersdorff, Olaf; Bonacina, Ilario; Chew, Leroy; Pich, Jan
1
2020
Lower bound techniques for QBF expansion. Zbl 07189478
Beyersdorff, Olaf; Blinkhorn, Joshua
1
2020
New resolution-based QBF calculi and their proof complexity. Zbl 07143742
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
1
2019
A game characterisation of tree-like Q-resolution size. Zbl 1425.03028
Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek
1
2019
Reasons for hardness in QBF proof systems. Zbl 07278086
Beyersdorff, Olaf; Hinde, Luke; Pich, Ján
1
2018
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. Zbl 1390.68015
Beyersdorff, Olaf (ed.); Wintersteiger, Christoph M. (ed.)
1
2018
Lifting QBF resolution calculi to DQBF. Zbl 06623530
Beyersdorff, Olaf; Chew, Leroy; Schmidt, Renate A.; Suda, Martin
1
2016
The complexity of theorem proving in autoepistemic logic. Zbl 1390.03045
Beyersdorff, Olaf
1
2013
Proof systems that take advice. Zbl 1222.03062
Beyersdorff, Olaf; Köbler, Johannes; Müller, Sebastian
1
2011
Proof complexity of propositional default logic. Zbl 1306.68183
Beyersdorff, Olaf; Meier, Arne; Müller, Sebastian; Thomas, Michael; Vollmer, Heribert
1
2010
The deduction theorem for strong propositional proof systems. Zbl 1202.03064
Beyersdorff, Olaf
1
2010
Proof complexity of non-classical logics. Zbl 1284.03257
Beyersdorff, Olaf
1
2010
Characterizing the existence of optimal proof systems and complete sets for promise classes. Zbl 1248.03059
Beyersdorff, Olaf; Sadowski, Zenon
1
2009
Does advice help to prove propositional tautologies? Zbl 1247.03119
Beyersdorff, Olaf; Müller, Sebastian
1
2009
Disjoint NP-pairs and propositional proof systems. Zbl 1119.03059
Beyersdorff, Olaf
1
2006
Disjoint NP-pairs from propositional proof systems. (Extended abstract). Zbl 1148.68379
Beyersdorff, Olaf
1
2006
Hardness characterisations and size-width lower bounds for QBF resolution. Zbl 07299470
Beyersdorff, Olaf; Blinkhorn, Joshua; Mahajan, Meena
1
2020
Frege systems for quantified Boolean logic. Zbl 07273080
Beyersdorff, Olaf; Bonacina, Ilario; Chew, Leroy; Pich, Jan
1
2020
Lower bound techniques for QBF expansion. Zbl 07189478
Beyersdorff, Olaf; Blinkhorn, Joshua
1
2020
Size, cost, and capacity: a semantic technique for hard random qbfs. Zbl 07029312
Beyersdorff, Olaf; Blinkhorn, Joshua; Hinde, Luke
4
2019
New resolution-based QBF calculi and their proof complexity. Zbl 07143742
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
1
2019
A game characterisation of tree-like Q-resolution size. Zbl 1425.03028
Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek
1
2019
Are short proofs narrow? QBF resolution is not so simple. Zbl 1407.03072
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
4
2018
Understanding cutting planes for QBFs. Zbl 06944937
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
2
2018
Reasons for hardness in QBF proof systems. Zbl 07278086
Beyersdorff, Olaf; Hinde, Luke; Pich, Ján
1
2018
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. Zbl 1390.68015
Beyersdorff, Olaf (ed.); Wintersteiger, Christoph M. (ed.)
1
2018
Feasible interpolation for QBF resolution calculi. Zbl 1448.68456
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
4
2017
Shortening QBF proofs with dependency schemes. Zbl 06807231
Blinkhorn, Joshua; Beyersdorff, Olaf
2
2017
Lower bounds: from circuits to QBF proof systems. Zbl 1334.68084
Beyersdorff, Olaf; Bonacina, Ilario; Leroy, Chew
9
2016
Understanding Gentzen and Frege systems for QBF. Zbl 1395.03028
Beyersdorff, Olaf; Pich, Ján
6
2016
Understanding cutting planes for QBFs. Zbl 1391.03041
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
2
2016
Are short proofs narrow? QBF resolution is not simple. Zbl 1388.03053
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
2
2016
Lifting QBF resolution calculi to DQBF. Zbl 06623530
Beyersdorff, Olaf; Chew, Leroy; Schmidt, Renate A.; Suda, Martin
1
2016
Proof complexity of resolution-based QBF calculi. Zbl 1355.68105
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
21
2015
A game characterisation of tree-like Q-resolution size. Zbl 1425.03027
Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek
6
2015
Feasible interpolation for QBF resolution calculi. Zbl 1440.68320
Beyersdorff, Olaf; Chew, Leroy; Mahajan, Meena; Shukla, Anil
5
2015
On unification of QBF resolution-based calculi. Zbl 1426.68283
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
19
2014
Unified characterisations of resolution hardness measures. Zbl 1423.68409
Beyersdorff, Olaf; Kullmann, Oliver
3
2014
A characterization of tree-like resolution size. Zbl 1285.68058
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
10
2013
Parameterized complexity of DPLL search procedures. Zbl 1354.68105
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
6
2013
The complexity of theorem proving in autoepistemic logic. Zbl 1390.03045
Beyersdorff, Olaf
1
2013
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
5
2012
The complexity of reasoning for fragments of default logic. Zbl 1267.68222
Beyersdorff, Olaf; Meier, Arne; Thomas, Michael; Vollmer, Heribert
3
2012
Parameterized complexity of DPLL search procedures. Zbl 1330.68099
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
5
2011
Model checking CTL is almost always inherently sequential. Zbl 1220.68068
Beyersdorff, Olaf; Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Vollmer, Heribert
5
2011
Do there exist complete sets for promise classes? Zbl 1253.68138
Beyersdorff, Olaf; Sadowski, Zenon
2
2011
Proof complexity of propositional default logic. Zbl 1308.03057
Beyersdorff, Olaf; Meier, Arne; Müller, Sebastian; Thomas, Michael; Vollmer, Heribert
2
2011
Parameterized bounded-depth Frege is not optimal. Zbl 1334.03056
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander
2
2011
Proof systems that take advice. Zbl 1222.03062
Beyersdorff, Olaf; Köbler, Johannes; Müller, Sebastian
1
2011
A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games. Zbl 1379.03017
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo
6
2010
A tight Karp-Lipton collapse result in bounded arithmetic. Zbl 1351.03055
Beyersdorff, Olaf; Müller, Sebastian
2
2010
Proof complexity of propositional default logic. Zbl 1306.68183
Beyersdorff, Olaf; Meier, Arne; Müller, Sebastian; Thomas, Michael; Vollmer, Heribert
1
2010
The deduction theorem for strong propositional proof systems. Zbl 1202.03064
Beyersdorff, Olaf
1
2010
Proof complexity of non-classical logics. Zbl 1284.03257
Beyersdorff, Olaf
1
2010
The complexity of propositional implication. Zbl 1202.68207
Beyersdorff, Olaf; Meier, Arne; Thomas, Michael; Vollmer, Heribert
8
2009
Nondeterministic functions and the existence of optimal proof systems. Zbl 1171.68010
Beyersdorff, Olaf; Köbler, Johannes; Messner, Jochen
7
2009
The complexity of reasoning for fragments of default logic. Zbl 1247.68263
Beyersdorff, Olaf; Meier, Arne; Thomas, Michael; Vollmer, Heribert
4
2009
On the correspondence between arithmetic theories and propositional proof systems – a survey. Zbl 1168.03042
Beyersdorff, Olaf
3
2009
Nondeterministic instance complexity and proof systems with advice. Zbl 1234.03035
Beyersdorff, Olaf; Köbler, Johannes; Müller, Sebastian
3
2009
Characterizing the existence of optimal proof systems and complete sets for promise classes. Zbl 1248.03059
Beyersdorff, Olaf; Sadowski, Zenon
1
2009
Does advice help to prove propositional tautologies? Zbl 1247.03119
Beyersdorff, Olaf; Müller, Sebastian
1
2009
Tuples of disjoint \(\mathsf{NP}\)-sets. Zbl 1148.68021
Beyersdorff, Olaf
4
2008
A tight Karp-Lipton collapse result in bounded arithmetic. Zbl 1157.03032
Beyersdorff, Olaf; Müller, Sebastian
3
2008
Logical closure properties of propositional proof systems. (Extended abstract). Zbl 1139.03316
Beyersdorff, Olaf
2
2008
Classes of representable disjoint NP-pairs. Zbl 1118.68069
Beyersdorff, Olaf
8
2007
The deduction theorem for strong propositional proof systems. (Extended abstract). Zbl 1135.03347
Beyersdorff, Olaf
3
2007
Disjoint NP-pairs and propositional proof systems. Zbl 1119.03059
Beyersdorff, Olaf
1
2006
Disjoint NP-pairs from propositional proof systems. (Extended abstract). Zbl 1148.68379
Beyersdorff, Olaf
1
2006
all top 5

Cited by 82 Authors

28 Beyersdorff, Olaf
10 Lauria, Massimo
9 Meier, Arne
5 Chew, Leroy
5 Galesi, Nicola
5 Müller, Sebastian
4 Blinkhorn, Joshua
4 Thomas, Michael A.
4 Vollmer, Heribert
3 Egly, Uwe
3 Hinde, Luke
3 Köbler, Johannes
3 Lonsing, Florian
3 Mahajan, Meena
3 Sadowski, Zenon
3 Seidl, Martina
3 Şhukla, Anil K.
3 Slivovsky, Friedrich
3 Szeider, Stefan
3 Thapen, Neil
2 Bonacina, Ilario
2 Dose, Titus
2 Janota, Mikoláš
2 Lück, Martin
2 Marques-Silva, João P.
2 Nordström, Jakob
2 Peitl, Tomáš
2 Pudlák, Pavel
2 Schindler, Irina
2 Schmidt, Renate A.
2 Schneider, Thomas
2 Suda, Martin
2 Thomas, Michael D.
1 Angiulli, Fabrizio
1 Atserias, Albert
1 Belle, Vaishak
1 Ben-Eliyahu-Zohary, Rachel
1 Bova, Simone
1 Chen, Yijia
1 Clarke, Edmund Melson jun.
1 Clemente, Lorenzo
1 Clymo, Judith
1 Dantchev, Stefan Stoyanov
1 Ebbing, Johannes
1 Fichte, Johannes Klaus
1 Flum, Jörg
1 Hsu, Tzu-Chien
1 Jiang, Jie-Hong Roland
1 Kauers, Manuel
1 Klieber, William
1 Krebs, Andreas
1 Kronegger, Martin
1 Kutz, Oliver
1 Lagniez, Jean-Marie
1 Lakemeyer, Gerhard
1 Lohmann, Peter
1 Lonca, Emmanuel
1 Marquis, Pierre
1 Martin, Barnaby D.
1 Mayr, Richard M.
1 Messner, Jochen
1 Müller, Moritz
1 Mundhenk, Martin
1 Palopoli, Luigi
1 Pfandler, Andreas
1 Pich, Ján
1 Rabe, Markus N.
1 Razborov, Aleksandr Aleksandrovich
1 Rodl, Vojtech
1 Schindler, Irena
1 Schmidt, Johannes
1 Schmidt, Johannes
1 Seshia, Sanjit Arunkumar
1 Sreenivasaiah, Karteek
1 Talebanfard, Navid
1 Torán, Jacobo
1 Tu, Kuan-Hua
1 Tzameret, Iddo
1 Van Gelder, Allen
1 Yap, Chee-Keng
1 Yukna, Stasys P.
1 Zhang, Liyu

Citations by Year