Inclusion-exclusion: exact and approximate
type: Item
instance of: scholarly article
title: Inclusion-exclusion: exact and approximate
zbMATH Open document ID: 0881.68084
DOI: 10.1007/BF01271266
published in: Combinatorica
publication date: 1998-01-11T00:00:00Z
review text: Given \(n\) events if the probabilities of all \(\leq k\)-wise intersections are given the probability of the union can be calculated within an error \(\exp \bigl( - \Omega(k^2/n)\bigr)\). This is optimal. Given a Boolean formula \(F\) in DNF with \(m\) clauses, if it is known how many assignments satisfy any choice of at most \(\log n +1\) clauses, the number of assignments satisfying \(F\) can be calculated. The results are applied to the edge reconstruction problem, computing permanents, chromatic polynomials, and problems on VC dimensions.
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05A20
zbMATH DE Number: 1102603
zbMATH Keywords: inclusion-exclusion formula
author: J. Kahn
author: Nathan Linial
author: Alex Samorodnitsky
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: A new method for generating Bonferroni-type inequalities by iteration
cites work: On the learnability of discrete distributions
cites work: Approximate inclusion-exclusion
cites work: A note on the line reconstruction problem
cites work: The edge reconstruction hypothesis is true for graphs with more than n log n edges
cites work: Q3851094
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
full work available at URL: https://doi.org/10.1007/bf01271266
OpenAlex ID: W1964537764
description: scientific article; zbMATH DE number 1102603