[Zurück]

S. Bova, F. Capelli, S. Mengel, F. Slivovsky:
"Knowledge Compilation Meets Communication Complexity";
Vortrag: International Joint Conference on Artificial Intelligence (IJCAI), New York, USA; 09.07.2016 - 15.07.2016; in: "Proceedings of the 25th International Joint Conference on Artificial Intelligence - IJCAI 2016", (2016), ISBN: 978-1-57735-770-4; S. 1008 - 1014.

Choosing a language for knowledge representation
and reasoning involves a trade-off between two competing
desiderata: succinctness (the encoding should
be small) and tractability (the language should support
efficient reasoning algorithms). The area of
knowledge compilation is devoted to the systematic
study of representation languages along these
two dimensions-in particular, it aims to determine
the relative succinctness of languages. Showing that
one language is more succinct than another typically
involves proving a nontrivial lower bound on the encoding
size of a carefully chosen function, and the
corresponding arguments increase in difficulty with
the succinctness of the target language. In this paper,
we introduce a general technique for obtaining
lower bounds on Decomposable Negation Normal
Form (DNNFs), one of the most widely studied
and succinct representation languages, by relating
the size of DNNFs to multi-partition communication
complexity. This allows us to directly translate
lower bounds from the communication complexity
literature into lower bounds on the size of DNNF
representations. We use this approach to prove exponential
separations of DNNFs from deterministic
DNNFs and of CNF formulas from DNNFs.

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