Set Disjointness

Given sets $S_1, \dots, S_N\subseteq [U]$ each of size at most $s$ and a set of $q$ queries $Q\subseteq [N]^2$ , report for each query $(i, j)\in Q$ whether $S_i\cap S_j = \emptyset$ .

Parameters

$|U|$ : size of universe
$N$ : number of sets
$s$ : bound on size of each set
$q$ : number of queries

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 2 of 2 reductions

			See more
3SUM	Set Disjointness	2023
Set Disjointness	Edge Triangle Counting	2016

Other relevant algorithms