{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaysofejhnp7uf2zzjolu3ov5cttouogd2qksutytp3thtzmgfnxy",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mh7ziukmkrz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.15463v1",
  "publishedAt": "2026-03-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Alexis de Colnet",
    "Alfons Laarman",
    "Joon Hyung Lee"
  ],
  "textContent": "**Authors:** Alexis de Colnet, Alfons Laarman, Joon Hyung Lee\n\nWe 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/2$ or if $δ> 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 thresholds for other CNF properties, namely, $δ= 1$ is the satisfiability threshold for 2-CNF while $δ= 1/2$ is the treewidth threshold, i.e., the point where the treewidth of the primal graph jumps from constant to linear in $n$ with high probability.",
  "title": "The Compilability Thresholds of 2-CNF to OBDD"
}