Implicit Decision Diagrams
Isaac Rudich, Louis-Martin Rousseau · 2026
Read Implicit Decision Diagrams by Isaac Rudich, Louis-Martin Rousseau (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-2602-20793.txt.
Description
Isaac Rudich and one co-author speed up decision diagrams, layered graphs used to bound and solve discrete optimization problems. Building a restricted diagram now costs width times log width per layer. A relaxed one costs width squared. Wider diagrams buy better bounds at a steep price in time and memory.
Their implicit diagrams store arcs implicitly rather than explicitly. That cuts both cases to width per layer, which they prove optimal when state updates and merges are treated as black boxes. The team also shows how implicit diagrams can drive a MIP solver, and releases ImplicitDDs, an open-source Julia solver that beats Gurobi on Subset Sum in their tests.
Catalog record
| CREATOR | Isaac Rudich, Louis-Martin Rousseau |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-20793