The treewidth of proofs
From MaRDI portal
Publication:2013559
DOI10.1016/J.IC.2017.05.005zbMATH Open1423.03244OpenAlexW2694154901WikidataQ114667612 ScholiaQ114667612MaRDI QIDQ2013559FDOQ2013559
Authors: Moritz Müller, Stefan Szeider 
Publication date: 8 August 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2017.05.005
Recommendations
- Revisiting space in proof complexity: treewidth and pathwidth
- scientific article; zbMATH DE number 7561762
- Tree-width in algebraic complexity
- Quantified propositional logic and the number of lines of tree-like proofs
- The Complexity of Propositional Proofs
- The Complexity of Propositional Proofs
- scientific article; zbMATH DE number 1860672
- scientific article; zbMATH DE number 1156870
- Lifting lower bounds for tree-like proofs
- scientific article; zbMATH DE number 785053
Cites Work
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Infinite Games
- Title not available (Why is that?)
- A partial k-arboretum of graphs with bounded treewidth
- Searching and pebbling
- Directed tree-width
- Parametrized complexity theory.
- Can you beat treewidth?
- Digraphs
- Combinatorics of first order structures and propositional proof systems
- Logical foundations of proof complexity
- The relative efficiency of propositional proof systems
- The vertex separation number of a graph equals its path-width
- Short proofs are narrow—resolution made simple
- A complexity gap for tree resolution
- Relativization makes contradictions harder for resolution
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Computer Science Logic
- Resolution lower bounds for the weak functional pigeonhole principle.
- On the weak pigeonhole principle
- Title not available (Why is that?)
- The limits of tractability in resolution-based propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- The Complexity of Propositional Proofs
- Space Complexity in Propositional Calculus
- On digraph width measures in parameterized algorithmics
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Title not available (Why is that?)
- A new proof of the weak pigeonhole principle
- Digraph decompositions and monotonicity in digraph searching
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- A combinatorial characterization of resolution width
- Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
- Optimality of size-width tradeoffs for resolution
- Short resolution proofs for a sequence of tricky formulas
- Narrow proofs may be spacious: separating space and width in resolution
- Size-space tradeoffs for resolution
- A New Kind of Tradeoffs in Propositional Proof Complexity
- From Small Space to Small Width in Resolution
- Partially definable forcing and bounded arithmetic
- Revisiting space in proof complexity: treewidth and pathwidth
- Parity Games and Propositional Proofs
- Time-space tradeoffs in resolution
Cited In (4)
This page was built for publication: The treewidth of proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013559)
