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 > Isaac Newton Institute Seminar Series > The complexity of enumeration and counting for acyclic conjunctive queries

## The complexity of enumeration and counting for acyclic conjunctive queriesAdd to your list(s) Download to your calendar using vCal - Durand, A (Universit Denis Diderot)
- Tuesday 27 March 2012, 14:00-15:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing Enumerating all the solutions of a problem or counting the number of these solutions are two related algorithmic tasks. Complexity measures, however, are of a different nature. For enumeration problem, for example, one of the main notion is that of delay between generated solutions. A problem is considered as tractable if one can enumerate the solutions one by one without repetition with a “reasonable” delay (e.g. polynomial, linear or constant time) between two solutions. In this talk, we will make a tour on the complexity of enumeration and (weighted) counting for acyclic conjunctive queries (ACQ), a well-known tractable fragment (for decision) of conjunctive queries. We first show that there is a dichotomy for enumeration and, up to some reasonable complexity assumption, such queries are either enumerable with a linear or with a “constant” delay. Hence, in all cases, enumeration is tractable. For weighted counting, the situation is more complex. The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it #P-hard. By introducing some polynomial representation of queries, we first show that weighted counting for quantifier-free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions of ACQ queries. This completely determine the tractability frontier for weighted counting in this case. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsThinking Society: Is our university a place of free thinking? Cambridge Society for the Application of Research (CSAR) CUUEG Talks## Other talksCoatable photovoltaics (Title t o be confirmed) Flow Cytometry The world is not flat: towards 3D cell biology and 3D devices SciBar: Sleep, Dreams and Consciousness Positive definite kernels for deterministic and stochastic approximations of (invariant) functions A rose by any other name Horizontal transfer of antimicrobial resistance drives multi-species population level epidemics “Modulating Tregs in Cancer and Autoimmunity” A new proposal for the mechanism of protein translocation Katie Field - Symbiotic options for the conquest of land Cambridge - Corporate Finance Theory Symposium September 2018 - Day 2 |