On the Hardness of Set Disjointness and Set Intersection with Bounded Universe

Isaac Goldstein, Moshe Lewenstein, Ely Porat

In the SetDisjointness problem, a collection of $m$ sets $S_1,S_2,...,S_m$ from some universe $U$ is preprocessed in order to answer queries on the emptiness of the intersection of…