Program

Jeremias conducted his research at the University of Helsinki under the supervision of Matti Järvisalo. The thesis brings substantial improvements to the state of the art in MaxSAT solving with both theoretical and practical contributions, ranging from preprocessing solving techniques to encodings for specific relevant application problems.

The first part of the thesis summarizes four contributions on improving pre-processing for MaxSAT. A significant contribution was to study the theoretical properties of MaxSAT pre-processing, showing that it cannot improve the best-case performance of either core-guided or hitting-set based approaches to MaxSAT, in terms of number of solve iterations, while it can improve the worst-case performance. This is an important result showing why preprocessing is vital in MaxSAT.

In the second part of the thesis, new MaxSAT encodings are proposed for two important data analysis tasks: correlation clustering and bounded treewidth Bayesian network learning. The first shows how MaxSAT can provide an exact approach to correlation clustering problems, that is significantly faster than other exact methods, and the quality of solutions obtained using MaxSAT is often significantly higher than the quality of solutions obtained by approximative (inexact) algorithms. This work defines a new state-of-the-art for correlation clustering. The second contribution examines MaxSAT models for learning bounded treewidth Bayesian networks. This is a very challenging problem, with few known solutions, that requires an intricate model to define.

As well as impressive papers arising from his thesis, he has additional papers as first author and as a co-author before obtaining his PhD. He developed several open-source software and MaxSAT benchmark sets that are openly available to the community and have been used in the MaxSAT Evaluation since 2015.

Peter conducted his research at the University of Oxford under the supervision of Stanislav Živný. The thesis contains three significant contributions to the theoretical understanding of the complexity of constraint satisfaction languages. Individually and together they show a deep understanding and ability to extend our knowledge of some of the most technical aspects of the field.

To best explain the quality of Peter’s contributions, we can do no better than quote from a recommendation letter by Martin Cooper:

“A natural way to define subproblems of the generic finite-domain optimisation problem known as the VCSP (Valued Constraint Satisfaction Problem) is to restrict the cost functions (valued constraints) that may occur in an instance to some language. The recent proof of the Feder and Vardi conjecture, independently by Bulatov and Zhuk, demonstrating that there is a dichotomy concerning the tractability of constraint languages, implied a similar dichotomy for valued constraint languages. This landmark result nevertheless left many questions unanswered. In his thesis Peter

Fulla has studied and made significant contributions to the following three questions:

1. Is the dichotomy valid for infinite languages?
2. How is the dichotomy affected by the extra restriction of planarity of the incidence graph of the instance?
3. How is the dichotomy affected by the extra global constraint of surjectivity?

For each of these questions, Peter Fulla has made a contribution which, on its own, would be worthy of a doctorate, as demonstrated by publications in premier theory conferences and journals. Together these three contributions form an impressive addition to the theory of tractability of finite-domain optimisation problems.”

As well as the outstanding work in his thesis, it is also clear that Peter is an outstanding collaborator who at an early stage in his PhD career was making significant contributions to his colleagues’ work, who said that “the acknowledgement he gets in that paper doesn’t give justice to his contribution”.