Avraham A. Melkman
e-mail: melkman@cs.bgu.ac.il
Solomon Eyal Shimony
e-mail: shimony@cs.bgu.ac.il
Ben-Gurion University - Math. and Comp. Sci. Dept.
P. O. Box 653
84105 Be'er Sheva, Israel
FAX : +972-7-472909
Given a sequence of n sets, it was shown by Kahn, Linial and Samorodnitsky that if it is known that u, the size of the union of all the sets, is less than 2^(n-1), then it can be determined uniquely from just the sizes of the intersections (but without knowing the size of the intersection of all n sets). Since their proof was existential they posed the question of finding an adaptive procedure for determining $u$. Here we present such an algorithm, and discuss the proof of some exact bounds on the intersection sizes when the above conditions do not hold.
Inclusion-exclusion, DNF model counting.
Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica, (in print).
Nathan Linial and Noam Nisan. Approximate inclusion-exclusion. Combinatorica, 10:349-365, 1990.
Short version of paper - to appear in Discrete Applied Mathematics.Long version of this paper is available in (PostScript) format.