-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Lemma 4 of doi.org/10.1016/j.tcs.2005.09.013 yields an $\Omega(n^2)$ deterministic lower bound for a single pass. An $\Omega(n)$ randomized lower bound for USTCON follows from a bipartite graph with special vertices $s$ and $t$ in one part and $n-2$ vertices in the other part $Y$, with $u \in Y$ connected to $s$ and $t$ depending on the bits held by Alice and Bob, respectively, in an instance of set non-disjointness. (See also dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.148 for a reduction from IP.) I am not aware of $\Omega(n^2)$ randomized lower bounds, even for one-way protocols. $\endgroup$ – András Salamon Jun 30 '18 at 17:25
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The problem with the initial USTCON reduction in this answer is that if $x_i=1$ then $G$ has an undirected st-path, but not vice versa: the odd length path linking $f_l[i]$ and $f_r[i]$ can go via other vertices. A trivial deterministic streaming algorithm tracks the connected components and checks if $s$ and $t$ are in the same component, using at most $n\lceil \lg n \rceil$ bits, so a tight $\Theta(n\lg n)$ is the space required for USTCON. Instead, the STCON reduction can be made to work directly by modifying your construction to use directed edges, showing the $\Omega(n^2)$ lower bound. $\endgroup$ – András Salamon Jul 4 '18 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.