COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries

## One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive QueriesAdd to your list(s) Download to your calendar using vCal - Hubert Chen, Birkbeck University of London
- Friday 27 April 2018, 14:00-15:00
- FW26.
If you have a question about this talk, please contact Victor Gomes. We study the classical problem of conjunctive query evaluation. This problem admits multiple formulations and has been studied in numerous contexts; for example, it is a formulation of the constraint satisfaction problem, as well as the problem of deciding if there is a homomorphism from one relational structure to another (which transparently generalizes the graph homomorphism problem). We here restrict the problem according to the set of permissible queries; the particular formulation we work 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 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 ). After presenting these advances, we will compare this line of research with another that aims to classify the complexity of the homomorphism problem where the second (target) structure is fixed, and that is currently being studied using universal-algebraic methods. We will also present and discuss two intriguing variants, injective homomorphism (also called embedding) and surjective homomorphism. This talk is mostly based on joint work with Moritz MÃ¼ller. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Computer Laboratory talks
- Computing and Mathematics
- FW26
- Logic and Semantics Seminar (Computer Laboratory)
- School of Technology
Note that ex-directory lists are not shown. |
## Other listsThe Inaugural Kate Pretty Lecture Triple Helix Cambridge Tagliaferri Lecture## Other talksOverview of Research Process Undersampling in physical imaging inverse problems Joseph Banks: science, culture and the remaking of the Indo-Pacific world Polynomial approximation of high-dimensional functions on irregular domains Macrophage-derived extracellular succinate licenses neural stem cells to suppress chronic neuroinflammation Cosmological Probes of Light Relics |