BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY: Simplifying inclusion-exclusion formulas
DTSTART:20120920T140000
DTEND:20120920T150000
DTSTAMP:20260407T183500Z
UID:d1c6c6354633cba2b14e58cfa187d16a329279b3d472952e4b327b14
CATEGORIES:Conferences - Seminars
DESCRIPTION:Xavier Goaoc\, INRIA\n\n\nAbstract:\nThe classical inclusion-e
 xclusion formula expresses the measure of\nthe union of a family of $n$ se
 ts using the measures of the\nintersections of subfamilies. The number of 
 terms in this formula is\nexponential in $n$\, and a significant amount of
  research\, originating\nin applied areas\, has been devoted to constructi
 ng simpler formulas\nfor particular families (e.g. sets of balls or halfsp
 aces).\n\nWe provide the apparently first upper bound valid for an arbitra
 ry\nfamily: we show that every system of $n$ sets with $m$ nonempty fields
 \nin the Venn diagram admits an inclusion-exclusion formula with\n$m^{O(\\
 log^2n)}$ terms and with $\\pm1$ coefficients\, and that such a\nformula c
 an be computed in $m^{O(\\log^2n)}$ expected time.\n\nThis is joint work w
 ith J. Matousek\, Pavel Patak\, Zuzana Safernova and\nMartin Tancer.\n\nht
 tp://arxiv.org/abs/1207.2591
LOCATION:MA B1 524
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR