Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I was reading a set of notes where it says
It can be shown that $\Omega(n^2)$ space is needed for one-pass algorithms to determine if an (unweighted, undirected) graph $G$ with $n$ nodes contains a triangle, even with randomization.
I've seen communication complexity results like that randomized protocols for disjointness require $\Omega(n)$ space, but what's a sketch or reference for the result above?
First, a streaming algorithm running in space $s(n)$ for a problem $C$ implies a communication protocol for $C$ using $s(n)$ bits of communication: Alice, on input $x$, runs the streaming algorithm on $x$ and then hands the configuration of the machine at the end of the stream to Bob ($s(n)$ bits), and then Bob, who has input $y$, runs the streaming algorithm starting from the provided configuration, and returns the result. Therefore, communication lower bounds imply streaming lower bounds.
Second, consider the following problem, called INDEX: Alice gets an $n$-bit string $x$ and Bob gets an integer $i \in [n]$, and they want to determine value of the $i$th bit of $x$, $x_i$. I'll quote the following result, which can be proved using an information statistics argument.
Claim 1: Any randomized (1/3-error, say) protocol for INDEX requires $\Omega(n)$ communication.
Now we can reduce from INDEX to the triangle-free problem. In particular, given and instance $(x, i)$ of INDEX we can build edge sets $E_A$ and $E_B$ over $V = L \cup R \cup \{s\}$ where $L = \{y_1, ..., y_{\sqrt{n}}\}$, $R = \{z_1, ..., z_{\sqrt{n}}\}$, and $s$ some constant node (so $2\sqrt{n} + 1 = O(\sqrt{n})$ nodes) with the property that the resulting graph $G$ is triangle-free iff $x_i = 1$. Additionally, Alice can compute $E_A$ herself and Bob can compute $E_B$ himself. To do this, pick some pairing function $p: [n] \to [\sqrt{n}] \times [\sqrt{n}]$ and say $p_L(k)$ is the first element in the pair corresponding to $p(k)$ and $p_R(k)$ is the second. We'll use this to map bit positions to edges. Then let $E_A = \{(y_{p_L(k)}, z_{p_R(k)})\ |\ x_k = 1\}$. Note that this is a bipartite graph. Now let $E_B = \{(s, y_{p_L(i)}), (s, z_{p_R(i)})\}$. $E_A$ has no triangles, and $E_B$ forms a triangle with $E_A$ only when theres an edge between $y_{p_L(i)}$ and $z_{p_R(i)}$, which only happens when $x_i = 1$.
An $o(n^2)$ communication-protocol for determining if a graph is triangle-free readily contradicts the INDEX lower bound: Alice gets $x$ and Bob gets $i$. Alice and Bob compute $E_A$ and $E_B$ respectively with no communication. They use the triangle-free protocol as a subroutine, using $o(\sqrt{n}^2) = o(n)$ communication.
