Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > APPROXIMATE DEGREE OF SYMMETRIC FUNCTIONS:
Reports tagged with Approximate degree of symmetric functions:
TR07-116 | 25th September 2007
Alexander A. Sherstov

#### 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 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