Hubie Chen: "One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries", LSV ENS Cachan, June 11th 2015, 10.30 am

Name: Hubie Chen
Title: One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries
Date and time: Thursday, June 11th 2015, at 10.30 am
Location: LSV library, ENS Cachan http://www.lsv.ens-cachan.fr/

Abstract: 
We study the classical problem of conjunctive query evaluation, here restricted according to the set of permissible queries.  In this work, this problem is formulated as the relational homomorphism problem over a set of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes and completely describe the resulting hierarchy given by this relation. This binary relation is defined in terms of a notion which we call graph deconstruction and which is a variant of the well-known notion of tree decomposition. We then use this graph hierarchy to infer a complexity hierarchy of homomorphism problems which is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized form of quantifier-free reductions. We obtain a significantly refined complexity classification of left-hand side restricted homomorphism problems, as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications, such as the classifications by Grohe-Schwentick-Segoufin (STOC 2001) and Grohe (FOCS 2003, JACM 2007).

In this talk, we will also briefly discuss parameterized complexity classes that we introduced/studied which capture  some of the complexity degrees identified by our classification.

This talk is based on joint work with Moritz Mûller that appeared in PODS ’13 and CSL-LICS ’14.