Parameterized and fine-grained knowledge compilation • Alexis de Colnet
- Advisor :
- Pierre Marquis
- Co-Supervisor :
- Stefan Mengel
The subject of the thesis is knowledge compilation, an approach for computationally hard problems that aims to work around general lower bounds results by preprocessing part of the input that is available in advance. In particular, it will be concerned with new approaches to knowledge compilation based on techniques from parameterized algorithms, approximation and fine-grained complexity. The results will complement known results from the literature and work around known hardness results by, instead of looking at problems in a worst-case setting, making refined analyses based on parameters or with relaxed requirements for the quality of the computed solutions.