Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

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 Prob [A_1 OR ... OR A_n] given Prob [AND_{i in S} A_i] for |S|{0,1} is a given symmetric function. (In the Linial-Nisan problem, f=OR.). We solve this general problem for every f 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 analyze, for every nonconstant symmetric f:{0,1}^n-Gt{0,1} and every epsin[2^{-n}, 1/3], the least degree deg_eps(f) of a polynomial that approximates f point wise within eps. Namely, we show that deg_eps(f) = tilde Theta (deg_{1/3}(f)+ sqrt{n log(1/eps)}), where deg_{1/3}(f) is well-known for each f. Previously, the answer for vanishing eps was known only for f=OR (Kahn et al.,1996; Buhrman et al., 1999). We construct the approximating polynomial explicitly for every f and eps. Our proof departs considerably from Linial and Nisan (1990) and Kahn et al. (1996). Its key ingredient is a classical result from approximation theory, which gives a certain equivalence of approximation and orthogonality in Euclideanspace. Our polynomial constructions feature new uses of Chebyshev polynomials.