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

bounded-depth Fregeparameterized complexityproof complexityresolution

Mathematics Subject Classification ID

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

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

(12)

• Tight size-degree bounds for sums-of-squares proofs
• Cliques enumeration and tree-like resolution proofs
• Parameterized bounded-depth Frege is not optimal
• Relativization makes contradictions harder for resolution
• Parameterized proof complexity
• Some definitorial suggestions for parameterized proof complexity
• Resolution and the binary encoding of combinatorial principles
• Narrow proofs may be maximally long
• Proof complexity and the binary encoding of combinatorial principles
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Kernelization, proof complexity and social choice
• Proof complexity of modal resolution

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)