TR07-116 Authors: Alexander A. Sherstov

Publication: 19th November 2007 14:55

Downloads: 1804

Keywords:

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.

Comment #1 Authors: Alexander A. Sherstov

Accepted on: 6th December 2007 23:27

Downloads: 2375

Keywords:

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.