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
| CREATOR | Alexis de Colnet, Alfons Laarman, Joon Hyung Lee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68708 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.15463