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.

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

http://publik.tuwien.ac.at/files/publik_254753.pdf

Created from the Publication Database of the Vienna University of Technology.