Lower Bounds for QBFs of Bounded Treewidth

DOI10.1145/3373718.3394756MaRDI QIDQ5145651zbMATH OpenOpenAlexFDO

Authors Johannes K. Fichte, Markus Hecher, Andreas Pfandler

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.01047

zbMATH Keywords

treewidthlower boundspathwidthparameterized complexityquantified Boolean formulasETH

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Recommendations

• A lower bound for treewidth and its consequences
• Treewidth computations. II. Lower bounds
• Bounded tree-width and LOGCFL
• Bounded Tree-Width and LOGCFL
• Lower bounds on the size of general branch-and-bound trees
• Treewidth with a quantifier alternation revisited
• Lower bound techniques for QBF expansion
• Bounded Tree-Width and CSP-Related Problems
• Faster algorithms for quantitative verification in bounded treewidth graphs
• Contraction and Treewidth Lower Bounds

Cited in

(9)

• Exploiting Database Management Systems and Treewidth for Counting
• Solving projected model counting by utilizing treewidth and its limits
• Utilizing treewidth for quantitative reasoning on epistemic logic programs
• Lifting lower bounds for tree-like proofs
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• scientific article; zbMATH DE number 7228403 (Why is no real title available?)
• Tight double exponential lower bounds
• A practical account into counting Dung's extensions by dynamic programming
• Reasoning in assumption-based argumentation using tree-decompositions

This page was built for publication: Lower Bounds for QBFs of Bounded Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145651)