Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph

Question

I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{1}{2}$, has space lower bound of $\Omega(n^2)$ bits, using techniques in communication complexity theory.

I believe what the problem intends me to do is to reduce s-t connectivity problem in directed graph to some problem with a well-established space lower bound in communication complexity theory. Basing on their space lower bounds, I guess I have to start with one of disjointness, indexing, or inner-product problem for two boolean vectors of length $n^2$, i.e. Alice has a $n^2$-length boolean vector $a$, with $a[i\times k+j]=1$ if and only if arc $(i,j) \in E$. This way if I can go on to complete the reduction of the problem to s-t connectivity problem, I can prove the $\Omega(n^2)$ bound, because all of the three problems has randomized communication complexity linear to their instance size.

However, I've been thinking for days and still have no clue about how to move forward from here... I would greatly appreciate some ideas or hints.

Answer 1

Consider the communication problem INDEX where Alice has a $n$ bit string $x_1x_2x_3...x_n$ and Bob has an index $i \in [n]$ where Bob's goal is to learn whether the bit $i$ of $x$ is $1$ or not.

It's known that this problem requires Alice to transmit at least $n$ bits to Bob.

Now we first construct a graph which has a path of length $3$ from $s$ to $t$ if and only if $x_i = 1$.

Consider the vertex set $V = s \cup A \cup B \cup t$ where $s$ and $t$ are single nodes while $A = \{a_1 , a_2 ,...,a_\sqrt{n}\} , B = \{b_1 , b_2 ,...,b_\sqrt{n}\}$ and edges set $E_{alice}$ and $E_{bob}$.

Now consider an injective map $f : [n] \rightarrow [\sqrt{n}] \times [\sqrt{n}]$, let $f_{l}[i]$ denote the first component of f while $f_{r}[i]$ denote the second component.

For every index $j$ where $x_j = 1$ , $E_{alice}$ has edge between $a_{f_l[j]}$ and $b_{f_r[j]}$. $E_{bob}$ has an edge between $s$ and $a_{f_l[i]}$ and also between $b_{f_r[i]}$ and $t$.

The graph $G = (V, E_{alice} \cup E_{bob})$ has a path from $s$ to $t$ of length 3 if and only $x_i = 1$.

To reduce this to directed connectivity, we take the vertex set $V$ and replace it with 4 copies of itself $V_0 , V_1 , V_2 , V_3$ and for every edge $(u,v) \in E_{alice} \cup E_{bob}$, we replace them with the directed edge $(u_i \rightarrow v_{i+1}) , i \in \{0,1,2\}$ where $v_i$ corresponds to node corresponding to $v \in V$ in $V_i$. Now $x_i = 1$ if and only if there is a (directed) path from $s_0$ to $t_3$.

The total number of nodes here is $8\sqrt{n} + 8$ so any sub-quadratic space streaming algorithm for s-t connectivity implies a sub-linear one-way communication protocol for the INDEX problem, which is not possible.