Parameterized bounded-depth Frege is not optimal

DOI10.1145/2355580.2355582MaRDI QIDQ2947567zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

resolutionparameterized complexityproof complexitybounded-depth Frege

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

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

Cited in

(11)

• Proof complexity of modal resolution
• Resolution and the binary encoding of combinatorial principles
• Some definitorial suggestions for parameterized proof complexity
• 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)