mlsanityData to 7 Oct 2026

SDDs are Exponentially More Succinct than OBDDs

arXiv 1601.00501 ↗First posted 4 Jan 2016cs.LOcited by 19

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 4; 2024: 6; 2025: 1; 2026: 4.

19 papers.

Sort:

  1. 2022On the Computation of Necessary and Sufficient Explanationscited by 23
  2. 2023Logic for Explainable AIcited by 23
  3. 2024Controllable Generation via Locally Constrained Resamplingcited by 11
  4. 2021Efficient Explanations for Knowledge Compilation Languagescited by 9
  5. 2022Tractable Boolean and Arithmetic Circuitscited by 9
  6. 2024Restructuring Tractable Probabilistic Circuitscited by 7
  7. 2023Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilationcited by 3
  8. 2024Explaining Decisions in ML Models: a Parameterized Complexity Analysiscited by 3
  9. 2024Canonical Decision Diagrams Modulo Theoriescited by 2
  10. 2026To Neuro-Symbolic Classification and Beyond by Compiling Description Logic Ontologies to Probabilistic Circuitscited by 2
  11. 2024Structured d-DNNF Is Not Closed Under Negationcited by 1
  12. 2026Neuro-symbolic Action Masking for Deep Reinforcement Learningcited by 1
7 more
  1. 2022Belief Revision in Sentential Decision Diagramscited by 0
  2. 2023Boosting-based Construction of BDDs for Linear Threshold Functions and Its Application to Verification of Neural Networkscited by 0
  3. 2023Variants of Tagged Sentential Decision Diagramscited by 0
  4. 2024Boolean Nearest Neighbor Language in the Knowledge Compilation Mapcited by 0
  5. 2025Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)cited by 0
  6. 2026A canonical generalization of OBDDcited by 0
  7. 2026Parameterized Complexity Of Representing Models Of MSO Formulascited by 0