Parameterized Compilation

Knowledge compilation offers a compelling approach to coping with computationally hard problems. This line of research was initiated in Theo early 1990s, and since then has become a very active and progressing field. Knowledge compilation proceeds in two phases: In Theo first phase Theo 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 Theo 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, Theo classical theory cannot provide reasonable guarantees for these problems. Theo 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 Theo key to this goal we propose to study knowledge compilation within Theo 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 Theo input in order to support Theo compilation. Hence we expect positive results in terms of upper bounds for compilation space and compilation time for problems that are not compilable in Theo classical sense. Theo proposed research will be driven by Theo study of concrete compilation problems that arise within broad areas like knowledge representation, abductive reasoning, logic programming, abstract argumentation, and propositional planning. Based on Theo insights gained from working on these concrete problems we will develop a rigorous approach to knowledge compilation that extends and refines Theo classical theory, and provides theoretical tools for parameterized upper and lower bounds. Theo theoretical objectives will be complemented by an empirical investigation on how parameters are distributed in real-world problem instances.

The research area of Knowledge Compilation (KC) offers a family of techniques and tools to successfully solve a variety of reasoning problems arising in computer science and artificial intelligence. The typical reasoning problem addressed by KC involves a stable piece of knowledge (for instance a catalogue of cars) which is queried multiple times in various and unpredictable ways (for instance by customers configuring their cars on the vendor online shop). The basic idea of KC is that of implementing the stable knowledge by specialized data structures over which the desired queries can be efficiently answered (customers demand for their queries to be answered quickly). The compilation stage periodically generates non-negligible costs for implementing the data structures, but these are amortized in the long run because the compiled information can be queried efficiently and is queried multiple times. The Parameterized Compilation project managed to push the theoretical limits of KC by several contributions, among which the following two deserve to be mentioned here. First, we developed the connection between KC and parameterized complexity, an approach allowing us to relativize negative results in KC by exploiting the structure of the piece of knowledge to be compiled. A basic example of negative result in KC is that propositional theories expressed in conjunctive normal form (CNF) do not admit succinct tractable representation, and hence knowledge bases in CNFs are not approachable within the KC paradigm. We pushed this kind of theoretical barrier by showing landmark results like that certain syntactic properties of CNFs, as well as of Boolean functions, guarantee succinct tractable representations. Second, we developed the theory of so-called tractable representations (in the par- lance above, data structures where certain target queries are feasible). Such a theory was partially settled by Darwiche and Marquis in a celebrated early-2000s paper on the so called KC Map, but not developed any further since then. A major contribution of the project is a substantial improvement of the state-of-the-art on tractable representation as presented in the KC map. This was made possible by a breakthrough connection between KC and an area of computational complexity called communication complexity.