Knowledge Compilation Meets Communication Complexity - Université d'Artois Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Knowledge Compilation Meets Communication Complexity

Simone Bova
  • Fonction : Auteur
Florent Capelli
Stefan Mengel
Friedrich Slivovsky
  • Fonction : Auteur

Résumé

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.
Fichier non déposé

Dates et versions

hal-03301001 , version 1 (27-07-2021)

Identifiants

  • HAL Id : hal-03301001 , version 1

Citer

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⟩
25 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More