The Compilability Thresholds of 2-CNF to OBDD

Alexis de Colnet, Alfons Laarman, Joon Hyung Lee · 2026

Read The Compilability Thresholds of 2-CNF to OBDD by Alexis de Colnet, Alfons Laarman, Joon Hyung Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15463.txt.

Description

De Colnet and co-authors prove two sharp thresholds for compiling random 2-CNF formulas into ordered binary decision diagrams. Clause density drives the split. Below density one half, or above one, small polynomial-size diagrams exist with high probability. Between those values, only exponential-size diagrams will do. Both thresholds echo known landmarks for random formulas. One matches the satisfiability threshold, and the other the treewidth threshold of the primal graph. The match, they note, is no accident.

Catalog record

CREATORAlexis de Colnet, Alfons Laarman, Joon Hyung Lee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68708
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.15463

Browse the full library · About the Tower of Babel