<p>As you might have realized by now, this problem is closely related to Matrix Multiplication.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-25T15:38:52.087Z
Hi mobius-dumpling, thank you for answer, yes the problem is reducible to instances of matrix multiplication.
XORwell
CC BY-SA 3.0
2013-12-26T07:10:49.573Z
Nice answer!  I noticed some typos.  "n by matrix X": do you mean "n by k matrix X"?  "m by m boolean product SX": do you mean "m by k boolean product SX"?
D.W.
CC BY-SA 3.0
2013-12-29T18:12:31.977Z
I'm not sure the ‘naive’ approach that solves the basic TASK in $O(n)$ is obvious. One way is to pre-compute a BDD for the function $f(x_1,\ldots,x_n)=\lor_{i=1}^m(\land_{j\in S_i}x_j)$ and then evaluate $f(\lnot X)$. (By $\lnot X$ I mean $x_k=1$ iff $k\notin X$.)
Radu GRIGore
CC BY-SA 3.0
2013-12-30T16:46:21.163Z
By computing a BDD or ZDD for family of sets $\{S_i\}_i$ we still have $O(mn)$ total time on query $X$, by considering worst-case ZDD-compression, haven't we ?
XORwell
CC BY-SA 3.0
2013-12-31T09:10:42.910Z
@XORwell: Building the BDD (not ZDD!) may even take exponential time (and space). But, once preprocessing is done, answering one query $X$ amounts to evaluating a BDD, which is $O(n)$, _not_ $O(mn)$.
Radu GRIGore
CC BY-SA 3.0
2013-12-25T00:31:03.980Z
2013-12-25T00:31:03.980Z
greg
<p>Here is how to solve the basic task in $O(n)$, at the expense of possibly lots of preprocessing. (This expands a comment I made.)</p>

<p><strong>Example.</strong> Suppose that $n$ is 3, and the given sets are {1,2}, {2,3}. Represent the boolean function $f(x_1,x_2,x_3)=(x_1\land x_2)\lor(x_2\land x_3)$ as a BDD:
$$f(x_1,x_2,x_3)=x_1?(x_2?1:0):(x_2?(x_3?1:0):0)$$
(Here $x?a:b$ means 'if $x$ then $a$ else $b$'.)
Clearly, evaluating $f$ written in this form takes time linear in $n$, which is possibly much smaller than the size of the input. The problem, of course, is that going from DNF to BDD may take an exponential amount of time (and space). But this is just preprocessing.</p>

<p>Suppose the query is the set {1}. We evaluate $f(0,1,1)$ to get 1, so we conclude that one of the given sets is disjoint from the query.</p>

<p>Suppose the query is the set {2}. We evaluate $f(1,0,1)$ to get 0, so we conclude that none of the given sets is disjoint from the query.</p>

<p><strong>The general case.</strong> Given sets $S_1,\ldots,S_m\subseteq[n]$, represent the function
$$f(x_1,\ldots,x_n)=\bigvee_{i=1}^m\bigwedge_{j\in S_i}x_j$$
as a (RO)BDD. To answer a query $X$ evaluate $f(x_1,\ldots,x_n)$ with $x_j=[j\notin X]$ for $1\le j\le n$.</p>

<p><strong>Comments.</strong> One way to view this construction is as a systematic way to precompute all answers. ‘Precompute all answers’ sounds dissatisfying, but I think the keyword should be ‘systematic’: it's not <em>a priori</em> obvious how to do it for this problem, given the comments on the question.</p>

<p>Another thing to note is that there are many negations going on here, which some people say are obvious, but they tend to make me dizzy. Probably the only reason I saw this construction quickly is that minutes before reading the question I was looking at the Monotone Duality problem, which is closely related to the question. Monotone Duality comes in many guises. One of them is Hitting-Sets: Given a family of sets, compute the family of all the hitting sets. This is clearly related to the question posed here, in which we are asked whether a given set is not a hitting set. (It's not the same though.) Another guise is Monotone-DNF-Dual: Given a monotone $f$ in DNF, find a $g$ in DNF such that $\lnot f(x_1,\ldots,x_m)=g(\lnot x_1,\ldots,\lnot x_m)$. I thought of the construction above because I knew that this is an equivalent formulation. So, perhaps a reference to a survey of the Monotone Duality problem would serve as a suitable reference:</p>

<ul>
<li>Eiter, Makino, Gottlob, <a href="http://scholar.google.co.uk/scholar?hl=en&amp;q=Computational%20Aspects%20of%20Monotone%20Dualization%3a%20A%20Brief%20Survey" rel="nofollow">Computational Aspects of Monotone Dualization: A Brief Survey</a>, 2007</li>
</ul>

<p>What does this construction say about lower bounds? Not much. But it does say that if you find a solution that answers a query in $O(h(m,n))$ time after $O(g(m,n))$ time preprocessing, then there exists a representation for monotone boolean functions that takes $O(g(m,n))$ space and allows evaluation in $O(h(m,n))$ time. For example, BDDs have exponential $g$ and $h(m,n)=n$. The reference for ‘exponential $g$’ is</p>

<ul>
<li>Hayase, Imai, <a href="http://scholar.google.co.uk/scholar?hl=en&amp;q=OBDDs%20of%20a%20monotone%20function%20and%20of%20its%20prime%20implicants" rel="nofollow">OBDDs of a monotone function and of its prime implicants</a>, 1996</li>
</ul>

<p><em>PS:</em> I would be grateful for any comments on how to improve this answer.</p>

CC BY-SA 3.0
2013-12-31T09:35:14.630Z
2014-01-01T12:39:21.977Z
2014-01-01T12:39:21.977Z
Radu GRIGore
<p>Consider the following empty intersection problem:</p>

<p><strong>INPUT</strong>: 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$ <br>
<strong>TASK</strong>: on query $X\subseteq [n]$ decide whether there exists $1\leq i\leq m$ s.t. $S_i\cap X = \emptyset$.<br>
<strong>TASKbis</strong>: on batch queries $X_1, \ldots, X_k\subseteq [n]$ decide whether $S_i\cap X_j=\emptyset$ for each $i,j$.</p>

<p>I'm in deep search for <strong><em>references</em></strong> 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...</p>

<p>Observe that we can impose special values of $m$, for example consider $m=n^2$, or similar ...</p>

CC BY-SA 3.0
2013-12-24T08:00:37.217Z
Is the problem typically dominated by n or by m? I guess I would have thought n all the way until you mentioned m = n^2 at the end, so maybe others have a similar question...
J Trana
CC BY-SA 3.0
2013-12-24T10:15:27.963Z
In the setting I have in mind, it is dominated by $m$, but by "small" polynomial factor, i.e. $m=O(n^2), m=O(n^3)$.
XORwell
CC BY-SA 3.0
2013-12-24T19:31:52.553Z
Ok, good to know. And can you bound n any further? While this may well be the theoretical CS site, there's still a huge difference between say n=32 and n=1024.
J Trana
CC BY-SA 3.0
2013-12-25T15:26:17.097Z
Hi Trana, no, in theory I would not bound $n$ any further, I would like to focus on asymptotic bounds in this setting.
XORwell
CC BY-SA 3.0
2013-12-25T23:23:06.060Z
The simplest case where $m=1$ is Set Disjointness, for which there are $\Omega(n)$ communication lower bounds (even in the randomized or approximate settings).
András Salamon
CC BY-SA 3.0
2013-12-26T07:07:32.060Z
Can you clarify the basic TASK?  You have a variable $i$ that is used without being defined.  Do you mean "on query $X$, decide whether $\exists i . S_i \cap X = \emptyset$"?  Do you mean "on query $X$, output a $m$-vector $x$ where $x_i=1$ if $S_i \cap X = \emptyset$ and $x_i=0$ otherwise"?  Something else?
D.W.
CC BY-SA 3.0
2013-12-27T22:33:46.053Z
Hi, thank you all for comments. D.W.: $\exists i$ @AndrásSalamon: I understand. Still, does this imply no way to improve over $O(mn)$, in case say $m=\Theta(\text{poly}(n))$, even in the  randomized / approximate setting ? I would say no, but I wait confirmation.
XORwell
CC BY-SA 3.0
2013-12-29T18:16:24.183Z
@XORwell: mobius dumpling hinted that an $O(n)$ (time) solution is possible, which would be an improvement over $O(mn)$.
Radu GRIGore
CC BY-SA 3.0
2013-12-30T16:51:24.217Z
You mean $O(n)$ time solution per query $X$ ? I think he means $O(n)$ per query $(X,S_i)$. Indeed, I would expect $O(m\text{poly}(\log n))$ at best, provided $m=\Omega(\text{poly}(n))$ ...
XORwell
CC BY-SA 3.0
2013-12-31T09:36:27.637Z
@XORwell: Yes, I mean $O(n)$ per query $X$. I added an answer with some details.
Radu GRIGore
<cc.complexity-theory><ds.algorithms>
Testing empty set intersection
XORwell
# Testing empty set intersection

(Asked by: username_0 on 2013-12-21)

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 ...

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: Is the problem typically dominated by n or by m? I guess I would have thought n all the way until you mentioned m = n^2 at the end, so maybe others have a similar question...  
> **username_0**: In the setting I have in mind, it is dominated by $m$, but by "small" polynomial factor, i.e. $m=O(n^2), m=O(n^3)$.  
> **username_1**: Ok, good to know. And can you bound n any further? While this may well be the theoretical CS site, there's still a huge difference between say n=32 and n=1024.  
> **username_0**: Hi Trana, no, in theory I would not bound $n$ any further, I would like to focus on asymptotic bounds in this setting.  
> **username_2**: The simplest case where $m=1$ is Set Disjointness, for which there are $\Omega(n)$ communication lower bounds (even in the randomized or approximate settings).  
> **username_3**: Can you clarify the basic TASK?  You have a variable $i$ that is used without being defined.  Do you mean "on query $X$, decide whether $\exists i . S_i \cap X = \emptyset$"?  Do you mean "on query $X$, output a $m$-vector $x$ where $x_i=1$ if $S_i \cap X = \emptyset$ and $x_i=0$ otherwise"?  Something else?  
> **username_0**: Hi, thank you all for comments. D.W.: $\exists i$ @AndrásSalamon: I understand. Still, does this imply no way to improve over $O(mn)$, in case say $m=\Theta(\text{poly}(n))$, even in the  randomized / approximate setting ? I would say no, but I wait confirmation.  
> **username_4**: @XORwell: mobius dumpling hinted that an $O(n)$ (time) solution is possible, which would be an improvement over $O(mn)$.  
> **username_0**: You mean $O(n)$ time solution per query $X$ ? I think he means $O(n)$ per query $(X,S_i)$. Indeed, I would expect $O(m\text{poly}(\log n))$ at best, provided $m=\Omega(\text{poly}(n))$ ...  
> **username_4**: @XORwell: Yes, I mean $O(n)$ per query $X$. I added an answer with some details.  

---

## 2 answers

### Answer by username_5 on 2013-12-25. Score: 6

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 << 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.

> **Comments:**
> **username_0**: Hi mobius-dumpling, thank you for answer, yes the problem is reducible to instances of matrix multiplication.  
> **username_3**: Nice answer!  I noticed some typos.  "n by matrix X": do you mean "n by k matrix X"?  "m by m boolean product SX": do you mean "m by k boolean product SX"?  
> **username_4**: I'm not sure the ‘naive’ approach that solves the basic TASK in $O(n)$ is obvious. One way is to pre-compute a BDD for the function $f(x_1,\ldots,x_n)=\lor_{i=1}^m(\land_{j\in S_i}x_j)$ and then evaluate $f(\lnot X)$. (By $\lnot X$ I mean $x_k=1$ iff $k\notin X$.)  
> **username_0**: By computing a BDD or ZDD for family of sets $\{S_i\}_i$ we still have $O(mn)$ total time on query $X$, by considering worst-case ZDD-compression, haven't we ?  
> **username_4**: @XORwell: Building the BDD (not ZDD!) may even take exponential time (and space). But, once preprocessing is done, answering one query $X$ amounts to evaluating a BDD, which is $O(n)$, _not_ $O(mn)$.  

---

### Answer by username_4 on 2013-12-31. Score: 4

Here is how to solve the basic task in $O(n)$, at the expense of possibly lots of preprocessing. (This expands a comment I made.)

**Example.** Suppose that $n$ is 3, and the given sets are {1,2}, {2,3}. Represent the boolean function $f(x\_1,x\_2,x\_3)=(x\_1\land x\_2)\lor(x\_2\land x\_3)$ as a BDD:
$$f(x\_1,x\_2,x\_3)=x\_1?(x\_2?1:0):(x\_2?(x\_3?1:0):0)$$
(Here $x?a:b$ means 'if $x$ then $a$ else $b$'.)
Clearly, evaluating $f$ written in this form takes time linear in $n$, which is possibly much smaller than the size of the input. The problem, of course, is that going from DNF to BDD may take an exponential amount of time (and space). But this is just preprocessing.

Suppose the query is the set {1}. We evaluate $f(0,1,1)$ to get 1, so we conclude that one of the given sets is disjoint from the query.

Suppose the query is the set {2}. We evaluate $f(1,0,1)$ to get 0, so we conclude that none of the given sets is disjoint from the query.

**The general case.** Given sets $S\_1,\ldots,S\_m\subseteq[n]$, represent the function
$$f(x\_1,\ldots,x\_n)=\bigvee\_{i=1}^m\bigwedge\_{j\in S\_i}x\_j$$
as a (RO)BDD. To answer a query $X$ evaluate $f(x\_1,\ldots,x\_n)$ with $x\_j=[j\notin X]$ for $1\le j\le n$.

**Comments.** One way to view this construction is as a systematic way to precompute all answers. ‘Precompute all answers’ sounds dissatisfying, but I think the keyword should be ‘systematic’: it's not *a priori* obvious how to do it for this problem, given the comments on the question.

Another thing to note is that there are many negations going on here, which some people say are obvious, but they tend to make me dizzy. Probably the only reason I saw this construction quickly is that minutes before reading the question I was looking at the Monotone Duality problem, which is closely related to the question. Monotone Duality comes in many guises. One of them is Hitting-Sets: Given a family of sets, compute the family of all the hitting sets. This is clearly related to the question posed here, in which we are asked whether a given set is not a hitting set. (It's not the same though.) Another guise is Monotone-DNF-Dual: Given a monotone $f$ in DNF, find a $g$ in DNF such that $\lnot f(x\_1,\ldots,x\_m)=g(\lnot x\_1,\ldots,\lnot x\_m)$. I thought of the construction above because I knew that this is an equivalent formulation. So, perhaps a reference to a survey of the Monotone Duality problem would serve as a suitable reference:

* Eiter, Makino, Gottlob, [Computational Aspects of Monotone Dualization: A Brief Survey](http://scholar.google.co.uk/scholar?hl=en&q=Computational%20Aspects%20of%20Monotone%20Dualization%3a%20A%20Brief%20Survey), 2007

What does this construction say about lower bounds? Not much. But it does say that if you find a solution that answers a query in $O(h(m,n))$ time after $O(g(m,n))$ time preprocessing, then there exists a representation for monotone boolean functions that takes $O(g(m,n))$ space and allows evaluation in $O(h(m,n))$ time. For example, BDDs have exponential $g$ and $h(m,n)=n$. The reference for ‘exponential $g$’ is

* Hayase, Imai, [OBDDs of a monotone function and of its prime implicants](http://scholar.google.co.uk/scholar?hl=en&q=OBDDs%20of%20a%20monotone%20function%20and%20of%20its%20prime%20implicants), 1996

*PS:* I would be grateful for any comments on how to improve this answer.


---

