Testing empty set intersection Consider the following empty intersection problem:

INPUT: a ground set $[n]:=\{1, \ldots, n\}$; a set family $S_1, \ldots, S_m$ s.t. $S_i\subseteq [n]$ for every $1\leq i\leq m$ 
TASK: on query $X\subseteq [n]$ decide whether there exists $1\leq i\leq m$ s.t. $S_i\cap X = \emptyset$.
TASKbis: on batch queries $X_1, \ldots, X_k\subseteq [n]$ decide whether $S_i\cap X_j=\emptyset$ for each $i,j$.

I'm in deep search for references about this problem, both TASK as well as the batched version TASKbis: fast algorithms (sequential, parallel, randomized, any other model is appreciated), also complexity lower bounds or other characterizations...

Observe that we can impose special values of $m$, for example consider $m=n^2$, or similar ...
As you might have realized by now, this problem is closely related to Matrix Multiplication.

Particularly: Task B asks to preprocess an m by n matrix S, such that given as a query a n by matrix X, we need to compute the m by m boolean product SX. For particularly structured matrices S, this can be solved by something like FFT. But I suspect that for a non-structured S (say random S) the best you could do is used fast matrix multiplication.

If the matrices S and X are sparse (i.e. the input sets are of cardinality &lt;&lt; n) then there are some algorithms for sparse matrix multiplication that can give some good results.

About the first task, it's of course even harder-looking, and I suspect that, unless the input S is of one of those special structures, the best approach is the naive one that takes O(n) time per query.