Efficient cardinality of set overlap relation
Consider the following problem. We are given $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,\log n\}$, and have to decide whether there are two disjoint sets among them. This problem is known as Orthogonal Vectors (OV), and it is conjectured that it cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon&gt;0$ (on a RAM machine). See for example Chen and Williams, An Equivalence Class for Orthogonal Vectors.