BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The complexity of enumeration and counting for acyclic conjunctive
  queries - Durand\, A (Universit Denis Diderot)
DTSTART:20120327T130000Z
DTEND:20120327T140000Z
UID:TALK37200@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Enumerating all the solutions of a problem or counting the num
 ber of these solutions are two related algorithmic tasks.  Complexity meas
 ures\, however\, are of a different nature. For enumeration problem\, for 
 example\, one of the main notion is that of delay between generated soluti
 ons. A problem is considered as tractable if one can enumerate the solutio
 ns one by one without repetition with a "reasonable" delay (e.g. polynomia
 l\, linear or constant time) between two solutions.\n\nIn this talk\, we w
 ill make a tour on the complexity of enumeration and\n(weighted) counting 
 for acyclic conjunctive queries (ACQ)\, a well-known tractable fragment (f
 or decision) of conjunctive queries.\n\nWe first show that there is a dich
 otomy for enumeration and\, up to some reasonable complexity assumption\, 
 such queries are either enumerable with a linear or with a "constant" dela
 y. Hence\, in all cases\, enumeration is tractable.\n\nFor weighted counti
 ng\, 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 tractab
 le 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 ass
 umption 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 t
 his case.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR