Lower Bounds for QBFs of Bounded Treewidth

DOI10.1145/3373718.3394756OpenAlexW3030023697MaRDI QIDQ5145651FDOQ5145651

Johannes K. Fichte, Andreas Pfandler, Markus Hecher

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

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

zbMATH Keywords

treewidthlower boundspathwidthparameterized complexityquantified Boolean formulasETH

Mathematics Subject Classification ID

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

Cited In (9)

• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs
• Exploiting Database Management Systems and Treewidth for Counting
• Solving projected model counting by utilizing treewidth and its limits
• 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?
• Title not available (Why is that?)
• 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)