Parameterized bounded-depth Frege is not optimal
From MaRDI portal
Publication:2947567
DOI10.1145/2355580.2355582zbMATH Open1322.68082OpenAlexW2092508401WikidataQ59902355 ScholiaQ59902355MaRDI QIDQ2947567FDOQ2947567
Authors: Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov 
Publication date: 24 September 2015
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2355580.2355582
Recommendations
- Parameterized bounded-depth Frege is not optimal
- Parameterized proof complexity
- Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Some definitorial suggestions for parameterized proof complexity
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Cited In (11)
- Resolution and the binary encoding of combinatorial principles
- Some definitorial suggestions for parameterized proof complexity
- Proof complexity of modal resolution
- Proof complexity and the binary encoding of combinatorial principles
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Parameterized bounded-depth Frege is not optimal
- Tight size-degree bounds for sums-of-squares proofs
- Narrow proofs may be maximally long
- Cliques enumeration and tree-like resolution proofs
- Relativization makes contradictions harder for resolution
- Parameterized proof complexity
This page was built for publication: Parameterized bounded-depth Frege is not optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947567)
