# SDDs are Exponentially More Succinct than OBDDs

arXiv: https://arxiv.org/abs/1601.00501 · HTML: https://mlsanity.com/paper/1601.00501/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2016.

## Built on by (most cited first, 19 of 19)

- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)
- [Efficient Explanations for Knowledge Compilation Languages](https://mlsanity.com/paper/2107.01654/) (2021)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation](https://mlsanity.com/paper/2303.06516/) (2023)
- [Explaining Decisions in ML Models: a Parameterized Complexity Analysis](https://mlsanity.com/paper/2407.15780/) (2024)
- [To Neuro-Symbolic Classification and Beyond by Compiling Description Logic Ontologies to Probabilistic Circuits](https://mlsanity.com/paper/2601.14894/) (2026)
- [Canonical Decision Diagrams Modulo Theories](https://mlsanity.com/paper/2404.16455/) (2024)
- [Structured d-DNNF Is Not Closed Under Negation](https://mlsanity.com/paper/2402.04832/) (2024)
- [Neuro-symbolic Action Masking for Deep Reinforcement Learning](https://mlsanity.com/paper/2602.10598/) (2026)
- [Belief Revision in Sentential Decision Diagrams](https://mlsanity.com/paper/2201.08112/) (2022)
- [Boosting-based Construction of BDDs for Linear Threshold Functions and Its Application to Verification of Neural Networks](https://mlsanity.com/paper/2306.05211/) (2023)
- [Variants of Tagged Sentential Decision Diagrams](https://mlsanity.com/paper/2312.00793/) (2023)
- [Boolean Nearest Neighbor Language in the Knowledge Compilation Map](https://mlsanity.com/paper/2410.06332/) (2024)
- [Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)](https://mlsanity.com/paper/2511.03545/) (2025)
- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)
- [Parameterized Complexity Of Representing Models Of MSO Formulas](https://mlsanity.com/paper/2604.08707/) (2026)

## Abstract (arXiv)

Introduced by Darwiche (2011), sentential decision diagrams (SDDs) are essentially as tractable as ordered binary decision diagrams (OBDDs), but tend to be more succinct in practice. This makes SDDs a prominent representation language, with many applications in artificial intelligence and knowledge compilation. We prove that SDDs are more succinct than OBDDs also in theory, by constructing a family of boolean functions where each member has polynomial SDD size but exponential OBDD size. This exponential separation improves a quasipolynomial separation recently established by Razgon (2013), and settles an open problem in knowledge compilation.