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
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.