Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
From MaRDI portal
Publication:5092411
DOI10.4230/LIPIcs.MFCS.2019.49OpenAlexW2971337465MaRDI QIDQ5092411
Dmitry Itsykson, Nicola Galesi, Anastasia Sofronova, Artur Riazanov
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10993/pdf/LIPIcs-MFCS-2019-49.pdf
Related Items (6)
Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ On tseitin formulas, read-once branching programs and treewidth ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Characterizing Tseitin-formulas with short regular resolution refutations
Cites Work
- Unnamed Item
- Satisfiability, branch-width and Tseitin tautologies
- Boolean function complexity. Advances and frontiers.
- Exponential lower bounds for the pigeonhole principle
- The treewidth of line graphs
- On tree-partition-width
- The intractability of resolution
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The complexity of the pigeonhole principle
- Simplified lower bounds for propositional proofs
- Resolution lower bounds for the weak functional pigeonhole principle.
- Hard examples for the bounded depth Frege proof system
- Cops-robber games and the resolution of Tseitin formulas
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Resolution lower bounds for perfect matching principles
- On Tseitin formulas, read-once branching programs and treewidth
- Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
- A Structure Theorem for Strong Immersions
- Excluded Grid Theorem
- Parity, circuits, and the polynomial-time hierarchy
- Polynomial size proofs of the propositional pigeonhole principle
- Hard examples for resolution
- Approximation and Small-Depth Frege Proofs
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP
- Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Resolution lower bounds for the weak pigeonhole principle
This page was built for publication: Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
