Simplifying inclusion-exclusion formulas
Event details
| Date | 20.09.2012 |
| Hour | 14:00 › 15:00 |
| Speaker | Xavier Goaoc, INRIA |
| Location |
MA B1 524
|
| Category | Conferences - Seminars |
Abstract:
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.
http://arxiv.org/abs/1207.2591
Links
Practical information
- Informed public
- Free
Organizer
- DCG, DisOpt