Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Simplifying inclusion-exclusion formulas   Let $\mathcal{F}=\{F_1,F_2, \ldots,F_n\}$ be a family of $n$ sets on a ground
set $S$, such as a family of balls in $\mathbb{R}^d$. For every finite measure
$\mu$ on $S$, such that the sets of $\mathcal{F}$ are measurable, the classical
inclusion-exclusion formula asserts that $\mu(F_1\cup F_2\cup\cdots\cup
F_n)=\sum_{I:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}\mu\Bigl(\bigcap_{i\in I}
F_i\Bigr)$; that is, the measure of the union is expressed using measures of
various intersections. 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
$\mathcal{F}$. We provide an upper bound valid for an arbitrary $\mathcal{F}$:
we show that every system $\mathcal{F}$ 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. For every $\varepsilon>0$ we also construct
systems with Venn diagram of size $m$ for which every valid inclusion-exclusion
formula has the sum of absolute values of the coefficients at least
$\Omega(m^{2-\varepsilon})$.

19
The categories of this paper are: eess
16
The categories of this paper are: stat
36
The categories of this paper are: cmp-lg
30
The categories of this paper are: q-alg
22
The categories of this paper are: chao-dyn
11
The categories of this paper are: hep-lat
24
The categories of this paper are: dg-ga
23
The categories of this paper are: solv-int
21
The categories of this paper are: adap-org
6
The categories of this paper are: astro-ph
34
The categories of this paper are: chem-ph
28
The categories of this paper are: alg-geom
26
The categories of this paper are: bayes-an
29
The categories of this paper are: funct-an
33
The categories of this paper are: plasm-ph
5
The categories of this paper are: gr-qc