Knowledge compilation (KC) is a research topic which aims to investigate the possibility of circumventing the computational intractability of hard tasks, by preprocessing part of the available information, common to a number of instances. Pioneered almost three decades ago, KC is nowadays a very active research field, transversal to several areas within computer science. Among others, KC intersects knowledge representation, constraint satisfaction, algorithms, complexity theory, machine learning, and databases.

The results obtained so far take various forms, from theory (compilability settings, definition of target languages for KC, complexity results, succinctness results, etc.) to more practical results (development and evaluation of compilers and other preprocessors, applications to diagnosis, planning, automatic configuration, etc.). Recently, KC has been positioned as providing a systematic method for solving problems beyond NP, and also found applications in machine learning.

The goal of this Dagstuhl Seminar is to advance both aspects of KC, and to pave the way for a fruitful cross-fertilization between the topics, from theory to practice. We target a mixture of long and short presentations, with discussions. Given the variety of aspects in knowledge compilation and the diversity of techniques used, some long talks with a tutorial flavor will be included in the program. We plan also to organize a demo session. We feel that the following topics are currently of particular importance, and we would like to focus on them in Dagstuhl:

• Knowledge Compilation and Parameterized Complexity
• Knowledge Compilation Maps
• Probabilistic Database Theory
• Building Knowledge Compilers
• Formats, Benchmarks, Empirical Protocols

Creative Commons BY 3.0 DE

Adnan Darwiche, Pierre Marquis, Dan Suciu, and Stefan Szeider

• Antoine Amarilli (Télécom ParisTech, FR) [dblp]
• Lameck Mbangula Amugongo (Namibia Univ. of Science & Technology - Windhoek, NA) [dblp]
• Paul Beame (University of Washington - Seattle, US) [dblp]
• Arpita Biswas (Indian Institute of Science - Bangalore, IN) [dblp]
• Pierre Bourhis (CNRS - Lille, FR) [dblp]
• Simone Bova (TU Wien, AT) [dblp]
• Florent Capelli (INRIA Lille, FR) [dblp]
• Ondrej Cepek (Charles University - Prague, CZ) [dblp]
• Zaineb Chelly Dagdia (Aberystwyth University, GB) [dblp]
• Arthur Choi (UCLA, US) [dblp]
• YooJung Choi (UCLA, US) [dblp]
• Adnan Darwiche (UCLA, US) [dblp]
• Ronald de Haan (University of Amsterdam, NL) [dblp]
• Hélène Fargier (University of Toulouse, FR) [dblp]
• Robert Ganian (TU Wien, AT) [dblp]
• Martin Grohe (RWTH Aachen, DE) [dblp]
• Henry A. Kautz (University of Rochester, US) [dblp]
• Batya Kenig (Technion - Haifa, IL) [dblp]
• Frederic Koriche (Artois University - Lens, FR) [dblp]
• Oliver Kullmann (Swansea University, GB) [dblp]
• Jean-Marie Lagniez (Artois University - Lens, FR) [dblp]
• Neha Lodha (TU Wien, AT) [dblp]
• Meena Mahajan (Institute of Mathematical Sciences - Chennai, IN) [dblp]
• Joao Marques-Silva (University of Lisbon, PT) [dblp]
• Pierre Marquis (Artois University - Lens, FR) [dblp]
• Wannes Meert (KU Leuven, BE) [dblp]
• Stefan Mengel (CNRS, CRIL - Lens, FR) [dblp]
• Shin-ichi Minato (Hokkaido University, JP) [dblp]
• Alexandre Niveau (Caen University, FR) [dblp]
• Jakob Nordström (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
• Dan Olteanu (University of Oxford, GB) [dblp]
• Igor Razgon (Birkbeck, University of London, GB) [dblp]
• Subhrajit Roy (IBM Research - Melbourne, AU) [dblp]
• Lisset Y. Salinas Pinacho (ifib - Bremen, DE)
• Scott Sanner (University of Toronto, CA) [dblp]
• Rahul Santhanam (University of Oxford, GB) [dblp]
• Marco Schaerf (Sapienza University of Rome, IT) [dblp]
• Pierre Senellart (ENS - Paris, FR) [dblp]
• Laurent Simon (University of Bordeaux, FR) [dblp]
• Friedrich Slivovsky (TU Wien, AT) [dblp]
• Dan Suciu (University of Washington - Seattle, US) [dblp]
• Stefan Szeider (TU Wien, AT) [dblp]
• Guy Van den Broeck (UCLA, US) [dblp]