Approximate inclusion-exclusion for arbitrary symmetric functions (Q626621)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximate inclusion-exclusion for arbitrary symmetric functions |
scientific article |
Statements
Approximate inclusion-exclusion for arbitrary symmetric functions (English)
0 references
18 February 2011
0 references
This paper proposes an algorithm for solving the approximation inclusion-exclusion problem on \(n\) events of a probability space. The article begins with a detailed introduction to inclusion-exclusion and approximation techniques used for its calculation including recent progress. This is followed by a lengthy section of useful theorems and propositions that help prove the main results and establish the properties of the proposed approximation. This useful and detailed article concludes with a section on the agnostic learning approach for which the proposed solution algorithm provides new lower bounds and a list of relevant references.
0 references
approximate inclusion-exclusion
0 references
approximate degree of Boolean function
0 references
approximation by polynomials
0 references