small size and small depth circuit for set intersections

Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$.

Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then do $S_1\cap S_a$. Next go to least element (say $b$) in $S_1\cap S_a$ and do $S_1\cap S_a \cap S_b$)

Finally I want to find the $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-1}}$ where $i_1$ least element in $S_1$ and $i_2$ least element in $S_1\cap S_{i_1}$, $i_3$ least element in $S_1\cap S_{i_1} \cap S_{i_2}$, $\cdots$, $i_{k-1}$ least element in $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-2}}$.

Can we build circuit for this above problem?

What happens if $k$ is fixed? what happens if $k$ is $\log n$?

Can we have logspace algorithm for this problem?

I tried as follows:

first construct a matrix $A$ with $n \times n$ with entries zero's and one's. Find the entry $(i,j)$ is one if $S_i$ have element $j$. other wise zero.

Now we need to find the first non zero entry (say a) in $S_1$ row in $A$ and do or gate $S_1$ row with $S_a$ row in $A$.
Again find the first non zero entry (say b) in $S_1 \vee S_a$ row and do $S_1\vee S_a \vee S_b$.

Now this process I can not able to find the depth and size of circuit. Please let me know what is the circuit size and depth in this process.

• I think you should be able to estimate the size and depth of your circuit given what you know. – Yuval Filmus May 23 '17 at 14:06
• When you say circuit, what exactly do you mean? Does the circuit have bounded fan-in or unbounded fan-in? What gates are allowed? – Yuval Filmus May 23 '17 at 14:06
• think in two cases 1) bounded fan-in 2) unbounded fan-in and gates only and ,or , not gates.... – GOLD May 23 '17 at 14:24
• @YuvalFilmus I did not find the depth and size of the following step in above process: "find the first non zero entry (say a) in S_1 row in A and do or gate S_1 row with S_a row in A." – GOLD May 23 '17 at 14:25
• I think it is within your capabilities to construct a circuit that computes $S_1 \cap S_a$. Just spend a few hours on it. – Yuval Filmus May 23 '17 at 18:23

You are asking many different questions. The usual rule is one question per post. To help you get started, here is how to compute $S_1 \cap S_{\min S_1}$ (defined as $\emptyset$ if $S_1 = \emptyset$).

The input to the circuit is the $n^2$ variables $x_{i,j}$, indicating $i \in S_j$ (this means that they are TRUE if the condition holds, and FALSE if it doesn't hold). The output to the circuit are $n$ variables $y_i$, indicating whether $i \in S_1 \cap S_{\min A}$.

Let $f_a$ indicate $\min S_1 = a$. Then $$f_a = \lnot x_{1,1} \land \cdots \land \lnot x_{a-1,1} \land x_a.$$ Given these, we can calculate $$y_i = x_{i,1} \land \bigvee_{a=1}^n (f_a \land x_{i,a}).$$ We can implement each $f_a$ as a depth 2 circuit with unbounded fan in of size $O(a)$, and each $y_i$ as a depth 2 circuit (with inputs $f_a$ and $x_{i,j}$) with unbounded fan in of size $O(n)$. The circuits for $f_a$ take $O(n^2)$ in total and the circuits for $y_i$ take $O(n^2)$ in total, so altogether we get a depth 4 circuit of size $O(n^2)$.

This circuit is equivalent to a depth $O(\log n)$ circuit of size $O(n^2)$ with bounded fan-in, by replacing each large fan-in gate by a balanced binary tree.

• Thanks and your answer helped me a lot. Is this total circuit for $S_1\cap S_{i_1} \cap S_{i_2}⋯\cap S_{i_k}$ has $4k$ depth and size $O(kn^2)$ ? If $k$ is fixed then circuit is in $AC_0$. If $k$ is at most $\log n$ then circuit is in $NC_1$. Am i right? – GOLD May 24 '17 at 9:57
• If $k$ is at most $\log n$ then the circuit is in $\mathsf{AC}^1 \subseteq \mathsf{NC}^2$. – Yuval Filmus May 24 '17 at 10:19
• Can we make circuit which is in $NC^1$ if $k$ is at most $\log n$? – GOLD May 25 '17 at 10:22
• Perhaps we can, perhaps we can't. – Yuval Filmus May 25 '17 at 20:20
• Can we show this problem is in $NL$-complete? if $k$ is at most $\log n$. I tried this problem is $NL$ or $NC^1$ but i did not. – GOLD Jun 1 '17 at 9:46