Infinite-Domain Constraint Satisfaction: Upper and Lower Complexity Bounds

Constraint Satisfaction Problems (CSP) are formalisms where relations restrict possible simultaneous values of variables.

Many important problems in, for instance, artificial intelligence, databases, graph theory, and operations research can be cast as CSPs. Practically interesting CSPs are typically NP-hard and are thus regarded to be intractable. However, realistic problem instances often contain "hidden structure" that can be exploited for efficient solving.

The prime method for studying hidden structure is parameterized complexity where complexity is measured via multiple parameters---this enables complexity analysis on a finer scale than in the classical setting.

We propose a 4-year project (based on the PI and one new PhD student) devoted to the theoretical study of parameterized complexity of CSPs over infinite variable domains: such CSPs encompass an abundance of highly relevant applications (such as temporal and spatial reasoning in artificial intelligence, linear and integer programming in operations research, and so on) but the parameterized complexity is far from well-studied when compared to finite-domain CSPs.

We will simultaneously work on obtaining upper and lower bounds on the parameterized complexity of relevant problems, and with the long-term goal on obtaining theoretical frameworks for such analysis.

In particular, we are interested in novel methods for algorithm construction---the algorithmic theory for infinite-domain CSPs is currently underdeveloped.