Réunion du 24 Janvier 2013

Jeudi 24 Janvier 2013
à Jussieu, Salle 211 (55-65)


10h30 Xavier Goaoc (Loria)
“Simplifying inclusion-exclusion formulas”

The classical inclusion-exclusion formula expresses the measure of
the union of a family of $n$ sets using the measures of the
intersections of subfamilies. The number of terms in this formula is
exponential in $n$, and a significant amount of research, originating
in applied areas, has been devoted to constructing simpler formulas
for particular families (e.g. sets of balls or halfspaces).

We provide the apparently first upper bound valid for an arbitrary
family: we show that every system of $n$ sets with $m$ nonempty fields
in the Venn diagram admits an inclusion-exclusion formula with
$m^{O(\log^2n)}$ terms and with $\pm1$ coefficients, and that such a
formula can be computed in $m^{O(\log^2n)}$ expected time.

This is joint work with J. Matousek, Pavel Patak, Zuzana Safernova and
Martin Tancer.


11h45 Buffet

14h — 18h Discussions et Groupes de travail

This entry was posted in Accueil. Bookmark the permalink.

Leave a Reply