BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:One Hierarchy Spawns Another: Graph Deconstructions and the Comple
 xity Classification of Conjunctive Queries - Hubert Chen\, Birkbeck Univer
 sity of London
DTSTART:20180427T130000Z
DTEND:20180427T140000Z
UID:TALK100087@talks.cam.ac.uk
CONTACT:Victor Gomes
DESCRIPTION:We study the classical problem of conjunctive query evaluation
 .  This problem admits multiple formulations and has been studied in numer
 ous contexts\; for example\, it is a formulation of the constraint satisfa
 ction problem\, as well as the problem of deciding if there is a homomorph
 ism from one relational structure to another (which transparently generali
 zes the graph homomorphism problem).\n\nWe here restrict the problem accor
 ding to the set of permissible queries\; the particular formulation we wor
 k with is 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 present a comprehensive complexity classi
 fication of these problems\, which strongly links graph-theoretic properti
 es of A to the complexity of the corresponding homomorphism problem. In pa
 rticular\, we define a binary relation on graph classes and completely des
 cribe the resulting hierarchy given by this relation. This binary relation
  is defined in terms of a notion which we call graph deconstruction and wh
 ich is a variant of the well-known notion of tree decomposition. We then u
 se this graph hierarchy to infer a complexity hierarchy of homomorphism pr
 oblems which is comprehensive up to a computationally very weak notion of 
 reduction\, namely\, a parameterized form of quantifier-free reductions. W
 e obtain a significantly refined complexity classification of left-hand si
 de restricted homomorphism problems\, as well as a unifying\, modular\, an
 d conceptually clean treatment of existing complexity classifications\, su
 ch as the classifications by Grohe-Schwentick-Segoufin (STOC 2001) and Gro
 he (FOCS 2003\, JACM 2007). \n\nAfter presenting these advances\, we will 
 compare this line of research with another that aims to classify the compl
 exity of the homomorphism problem where the second (target) structure is f
 ixed\, and that is currently being studied using universal-algebraic metho
 ds.  We will also present and discuss two intriguing variants\, injective 
 homomorphism (also called embedding) and surjective homomorphism.\n\nThis 
 talk is mostly based on joint work with Moritz Müller.
LOCATION:FW26
END:VEVENT
END:VCALENDAR