{"id":"arxiv/2603.15463","url":"https://arxiv.org/abs/2603.15463","tags":["cs.DS","cs.DM","math.CO","math.PR"],"score":0,"title":"The Compilability Thresholds of 2-CNF to OBDD","domain":"cs.DS","source":"arxiv","authors":["Alexis de Colnet","Alfons Laarman","Joon Hyung Lee"],"reviews":0,"subject":"cs.DS","summary":"We prove the existence of two thresholds regarding the compilability of random 2-CNF formulas to OBDDs. The formulas are drawn from $\\mathcal{F}_2(n,δn)$, the uniform distribution over all 2-CNFs with $δn$ clauses and $n$ variables, with $δ\\geq 0$ a constant. We show that, with high probability, the random 2-CNF admits OBDDs of size polynomial in $n$ if $0 \\leq δ 1$. On the other hand, for $1/2 < δ< 1$, with high probability, the random $2$-CNF admits only OBDDs of size exponential in $n$. It is no coincidence that the two ``compilability thresholds'' are $δ= 1/2$ and $δ= 1$. Both are known…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-16","reactions":{}}