Combinatorially and Algebraically Decomposing Search spaces: Better Worst-case Bounds for Hard Search Tasks

Search tasks are computational tasks with a curious property: while their solutions are easily verifiable when given, finding those solutions from scratch appears much more arduous. A central algorithmic paradigm to solve such tasks is that of search space decomposition.

This paradigm solves a search task by breaking it up in subtasks such that a solution to the original problem can be quickly recovered from solutions of the subtasks.

Despite its basic nature and its ubiquitous use, it still holds many mysteries.The mission of COALESCE is to develop a broad theory to design and analyze search space decompositions to solve fundamental search tasks as fast as possible in the standard model of worst-case analysis. Strikingly, such a theory has not been developed yet.

Our theory will be a coalescence of two established theories:- Combinatorial search space decompositions have been studied for graph problems in the area of width parameters, but only focus on decomposing the input and not the search space.- Algebraic decompositions such as factorizations of matrices and tensors that are of low rank or sparse, have been studied in the area of algebraic complexity, but only for very few problems and not in combination with search space decompositions.In this proposal, I identify concrete research problems from Parameterized and Fine-Grained Complexity (two prominent subfields of Theoretical Computer Science) that serve as stepping stones towards a model for search space decompositions beyond input decompositions, as well as a theory to analyse their algorithmic power based on combinatorial and algebraic decompositions.Now is the right moment for this project: the joint power of combinatorial and algebraic decompositions is still barely understood and not yet fully exploited.

COALESCE will combine these (and many more) tools in novel ways that transcend existing approaches, and bring a rich theory on the search space decomposition methods entirely within reach.