Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATE INCLUSION-EXCLUSION:
Reports tagged with Approximate inclusion-exclusion:
TR07-116 | 25th September 2007
Alexander A. Sherstov

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

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: ... more >>>




ISSN 1433-8092 | Imprint