Parameterized Compilation

Funding Organisation: The Austrian Science Funds, FWF
Project Number: FWF P26200

Project Team

• Simone Bova
• Ronald de Haan
• Neha Lodha
• Stefan Szeider (Principal Investigator)

Topic

Knowledge compilation offers a compelling approach to coping with computationally hard problems. This line of research was initiated in the early 1990s, and since then has become a very active and progressing field.  Knowledge compilation proceeds in two phases: In the first phase the input data is compiled into a new representation, which is then used in a second phase to execute a number of individual tasks efficiently.  Ideally, one aims at a compilation that causes only a polynomial increase in space, and the classical theory of compilation offers theoretical tools to decide whether such a compilation is possible or not.  However, systematic research shows that most relevant problems are not compilable with a polynomial increase in space. Hence, the classical theory cannot provide reasonable guarantees for these problems.

The goal of this project is to overcome this limit of classical knowledge compilation by utilizing structural aspects of problem inputs (such as as tree-likeness, degree of cyclicity, or backdoor size). As the key to this goal we propose to study knowledge compilation within the framework of parameterized complexity, which has become an important and successful research direction in algorithms and complexity. Parameterized complexity provides powerful methods and tools for exploiting structural aspects of problems and is therefore ideally suited for this purpose. Using parameters we can exploit structural aspects of the input in order to support the compilation. Hence we aim at positive results in terms of upper bounds for compilation space and compilation time for problems that are not compilable in the classical sense.

Events

kc-logoSymposium on New Frontiers in Knowledge Compilation

This symposium was organised by Pierre Marquis and Stefan Szeider and held in Vienna, Austria, June 4-6, 2015. The aim of this symposium was  to bring together researchers who work on knowledge compilation from various angles, including knowledge representation, constraints, theory of algorithms, complexity, machine learning, and databases, as well as researchers from related areas. Lectures and discussions have  put all these different approaches into context and stimulated a fruitful exchange of ideas between researchers from different fields. The symposium had over 30 participants and featured several invited and contributed talks.

More information can be found on the symposium homepage.

Dagstuhl Seminar on Recent Trends in Knowledge Compilation

Stimulated by the success of the Symposium in Vienna, another larger meeting on this topic was organized by Adnan Darwiche (UCLA, US),  Pierre Marquis (Artois University – Lens, FR), Dan Suciu (University of Washington – Seattle, US, and Stefan Szeider (TU Wien, AT). The seminar was held at Schloss Dagstuhl, Wadern, Germany,  September 17-22, 2017,

The seminar had over 40 participants and featured several invited and contributed talks as well as a demo session and and open problems session.

Among others, the seminar was an excellent occasion for disseminating results of the project, in terms of several talks.

A report on the seminar has been published as Dagstuhl Report (Volume 7, Issue 9, 2018).

More information can be found on the seminar homepage.