Talks and Poster Presentations (with Proceedings-Entry):
"SDDs Are Exponentially More Succinct than OBDDs";
Talk: AAAI Conference,
Phoenix, Arizona, USA;
- 2016-02-17; in: "Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence",
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
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 (2014a), and settles
an open problem in knowledge compilation (Darwiche 2011).
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.