Francesco Lupia

Research Abstract

A fundamental problem in the field of Artificial Intelligence and related disciplines, in particular Database theory, is the constraint satisfaction problem (CSP) which comes as a unifying framework to express a wide spectrum of computational problems. Examples include graph colorability, planning, and database queries. The goal is either to find one solution, to enumerate all solutions, or counting them. As a very general problem, it comes with no surprise that in most settings CSPs are hard to solve. Indeed considerable effort has been invested by the scientific community to shed light on the computational issues of this problem, with the objective of identifying easy instances (also called islands of tractability) and exploiting the knowledge derived from their solution to help solving the harder ones. My thesis investigates the role that structural properties play in the computational aspects of CSPs, describes algorithms to exploit such properties, and provides a number of specific tools to solve efficiently problems arising in database theory, game theory, and process mining.