Decision diagrams encode discrete optimization problems as directed acyclic graphs — each path from root to terminal represents a solution, and the structure enables pruning that exact methods cannot match. The standard implementation stores arcs explicitly: every connection between nodes is materialized in memory. For a diagram of width w and depth d, this means O(w²) work per layer to enumerate all possible arcs.
Rudich and Rousseau (arXiv:2602.20793) show that storing arcs implicitly — computing them on demand rather than enumerating them — reduces per-layer complexity to O(w). The improvement is a full factor of w. They prove this is optimal: any framework that treats state-update and merge operations as black boxes cannot do better.
The proof of optimality is the key contribution. It means the algorithmic frontier has been reached. Further improvement requires breaking the abstraction — exploiting structure inside the operations that the decision diagram framework treats as opaque. The focus shifts from algorithm design to implementation engineering.
The practical consequence: an open-source Julia solver built on implicit decision diagrams outperforms Gurobi on Subset Sum problems. Gurobi is one of the most engineered commercial optimization solvers. The implicit representation — a structural insight, not a new algorithm — beats brute engineering.
The general observation: the representation of a computation constrains its cost. The same algorithm — decision diagram with the same width and depth — has different complexity depending on whether arcs are explicit or implicit. The computation didn't change; the way it was stored did. Sometimes the bottleneck is not the algorithm but the data structure.