Inclusion-exclusion: exact and approximate

DOI10.1007/BF01271266zbMath0881.68084OpenAlexW1964537764MaRDI QIDQ1375692

Alex Samorodnitsky, Nathan Linial, Jeffry Kahn

Publication date: 11 January 1998

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01271266

zbMATH Keywords

inclusion-exclusion formula

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial probability (60C05) Combinatorial inequalities (05A20) Asymptotic enumeration (05A16)

Related Items (21)

A construction of combinatorial NLTS ⋮ Approximating real-rooted and stable polynomials, with combinatorial applications ⋮ Measures on Boolean polynomials and their applications in data mining ⋮ Approximate Model Counting via Extension Rule ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Efficient construction of a small hitting set for combinatorial rectangles in high dimension ⋮ Some Cardinal Estimations via the Inclusion-Exclusion Principle in Finite $$T_0$$ Topological Spaces ⋮ Simplifying Inclusion–Exclusion Formulas ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Algorithmic Polynomials ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ The hardest halfspace ⋮ A note on approximate inclusion--exclusion ⋮ Reliability evaluation of a multicast over coded packet networks ⋮ Two approximate algorithms for model counting ⋮ Using binary patterns for counting falsifying assignments of conjunctive forms ⋮ Inclusion-exclusion for \(k\)-CNF formulas ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Approximate inclusion-exclusion
• The edge reconstruction hypothesis is true for graphs with more than n log n edges
• A note on the line reconstruction problem
• On the learnability of discrete distributions
• A new method for generating Bonferroni-type inequalities by iteration
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Inclusion-exclusion: exact and approximate