Talks and Poster Presentations (with Proceedings-Entry):
S. Bova:
"SDDs Are Exponentially More Succinct than OBDDs";
Talk: AAAI Conference,
Phoenix, Arizona, USA;
2016-02-12
- 2016-02-17; in: "Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence",
(2016),
ISBN: 978-1-57735-760-5;
929
- 935.
English abstract:
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 (2014a), and settles
an open problem in knowledge compilation (Darwiche 2011).
Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_254753.pdf
Created from the Publication Database of the Vienna University of Technology.