No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth

DOI10.1007/978-3-319-13524-3_27zbMath1341.68065arXiv1407.0491OpenAlexW1933346394MaRDI QIDQ2946031

Igor Razgon

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (9)

On the read-once property of branching programs and CNFs of bounded treewidth ⋮ On Compiling Structured CNFs to OBDDs ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ On compiling structured CNFs to OBDDs ⋮ No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth ⋮ Lower bounds on the mim-width of some graph classes ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Parameterized Compilation Lower Bounds for Restricted CNF-Formulas ⋮ Connecting knowledge compilation classes and width parameters

Cites Work

• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• On lower bounds for read-\(k\)-times branching programs
• No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
• Treewidth in Verification: Local vs. Global

This page was built for publication: No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth