Seminar

Speaker:	Hubie Chen
Title:	One Hierarchy Spawns Another: The Complexity Classification of Conjunctive Queries
Date:	Παρασκευή, 28 Μάρ 2014
Ώρα:	18:30-19:30
Location:	Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, Τμήμα Μαθηματικών, room Γ33

Abstract

We study the problem of conjunctive query evaluation over sets of queries; this problem is formulated here as the relational homomorphism problem over a class of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We introduce a notion which we call graph deconstruction, which is a variant of the well-known notion of tree decomposition. Using this notion, we give a novel, modular, and conceptually clean presentation of the theorem describing the tractable homomorphism problems in the framework under study (assuming bounded arity). We then study a binary relation on graph classes that is naturally induced by the notion of graph deconstruction. We completely describe the hierarchy of graph classes that this binary relation yields, and discuss how this hierarchy of graph classes can be used to infer a complexity-theoretic hierarchy of homomorphism problems, which is extremely fine as it is exhaustive up to a computationally very weak notion of reduction (namely, a parameterized form of quantifier-free reduction). A version of the article on which this talk is based is available at: http://arxiv.org/abs/1307.1353