Let A_1,...,A_n be events in a probability space. The
approximate inclusion-exclusion problem, due to Linial and
Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given
Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve
this problem optimally for each k. We study the following more
general question: given Pr[AND_{i\in S}A_i] for all |S|<=k,
estimate
Pr[the number of events among A_1,...,A_n that hold is in Z],
where Z\subseteq{0,1,...,n} is a given set. (In the Linial-Nisan
problem, Z={1,...,n}.) We solve this general problem for all
Z and k, giving an algorithm that runs in polynomial time and
achieves an approximation error that is essentially optimal.
We prove this optimal error to be 2^{-\tilde\Theta(k^2/n)} for
k above a certain threshold, and Theta(1) otherwise.
As part of our solution, we determine, for every predicate
D:{0,1,...,n}->{0,1} and every epsilon\in[1/2^n, 1/3], the
least degree deg_{epsilon}(D) of a polynomial that approximates
D pointwise within epsilon. Namely, we show that
deg_{epsilon}(D)=\tilde\Theta(deg_{1/3}(D)+sqrt{n*log(1/epsilon)}),
where deg_{1/3}(D) is well-known for each D. Previously, the
answer for vanishing epsilon was known only for D=OR (Kahn et
al., 1996). We construct the approximating polynomial explicitly
for every D and epsilon.
Our proof departs considerably from Linial and Nisan (1990)
and Kahn et al. (1996). Its key ingredient is the
Approximation/Orthogonality Principle, a certain equivalence
of approximation and orthogonality in Euclidean space,
recently proved by the author in the context of quantum lower
bounds (Sherstov 2007). Our polynomial constructions feature
new uses of the Chebyshev polynomials.
An important tool in our recent work (ECCC reports TR07-100
and TR07-116) is the Approximation/Orthogonality Principle,
which we formulate and prove from scratch. We have learned
recently that this principle is actually a classical result
in the approximation literature. Thanks to James Lee,
Sasha Razborov, and Avi Wigderson for pointing this out!
We will include a detailed reference in all future revisions.
