[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Approximate Inclusion-Exclusion

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

The Inclusion-Exclusion formula expresses the size of a union of a family of sets in terms of the sizes of intersections of all subfamilies. This paper considers approximating the size of the union when intersection sizes are known for only some of the subfamilies, or when these quantities are given to within some error, or both.

In particular, we consider the case when allk-wise intersections are given for everyk≤K. It turns out that the answer changes in a significant way aroundK=√n: ifK≤O(√n) then any approximation may err by a factor of θ(n/K 2), while ifK≥ Ω(√n) it is shown how to approximate the size of the union to within a multiplicative factor of\(1 \pm e^{ - \Omega (K/\sqrt n )} \).

When the sizes of all intersections are only given approximately, good bounds are derived on how well the size of the union may be approximated. Several applications for Boolean function are mentioned in conclusion.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N.Alon, and J.Hastad: Private communication. 1988.

  2. M.Ajtai, and A.Wigderson: Deterministic simulation of probabilistic constant depth circuits, In 26 th Annual Symposium on Foundations of Computer Science, Portland, Oregon, (1985), 11–19.

  3. C. E.Bonferroni: Teoria statistica delle classi e calcolo dell probabilita, Involume in onore di Ricardo Dalla Volta, Universita di Firenze, (1937), 1–62.

  4. E. W.Cheney.:Approximation Theory, McGraw-Hill Book Co.,1966.

  5. S. M. Kwerel: Most stringent bounds on aggregated probabilities of partially specified dependent probability systems,J. Am. Stat. Assoc. 70, (1975), 472–479.

    Google Scholar 

  6. N.Nisan, and A.Wigderson: Hardness vs. randomness. In 29 th Annual Symposium on Foundations of Computer Science, White Plains, New York, October (1988), 2–12.

  7. A. Prékopa: Boole-Bonferroni inequalities and linear programming,Operation Research 36, (1988), 145–162.

    Google Scholar 

  8. Theodore J.Rivlin:An Introduction to the Approximation of Functions, Blaisdell Publishing Company,1969.

  9. H, J.Ryser:Combinatorial mathematics, The Mathematical Association of America,1963.

  10. L.G. Valiant: The complexity of computing the permanent,Theor. Comp. Sci.,8, (1979), 189–201.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM-Almaden, Stanford University, USA

    Nathan Linial

  2. Hebrew University, USA

    Nathan Linial

  3. Laboratory for Computer science, MIT, 545 Tech. sq., 02139, Cambridge, MA, USA

    Noam Nisan

Authors
  1. Nathan Linial
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Noam Nisan
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Partially supported by NSF 865727-CCR and ARO DALL03-86-K-017. Part of this work was done in U.C. Berkeley, supported by NSF CCR-8411954.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Linial, N., Nisan, N. Approximate Inclusion-Exclusion. Combinatorica 10, 349–365 (1990). https://doi.org/10.1007/BF02128670

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02128670

AMS subject classification (1980)

Search

Navigation