Skip to Main content Skip to Navigation
Conference papers

Knowledge Compilation Meets Communication Complexity

Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien Delorme Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 12:49:42 PM
Last modification on : Wednesday, November 3, 2021 - 9:13:32 AM


  • HAL Id : hal-03301001, version 1



Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky. Knowledge Compilation Meets Communication Complexity. 25th International Joint Conference on Artificial Intelligence (IJCAI'16), 2016, New York, NY, USA, Unknown Region. pp.1008--1014. ⟨hal-03301001⟩



Les métriques sont temporairement indisponibles