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

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

<p><strong>Claim 1</strong>: Any randomized (1/3-error, say) protocol for INDEX requires $\Omega(n)$ communication. </p>

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

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

CC BY-SA 4.0
2018-05-25T21:05:16.730Z
By the way, I think you mean to say $z_{P_L(k)}$ not $x_{P_L(k)}$.
Drew Brady
CC BY-SA 4.0
2018-05-25T20:03:54.873Z
2018-05-25T22:08:42.797Z
2018-05-25T22:08:42.797Z
Sam McGuire
<p>I was reading a set of notes where it says </p>

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

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

CC BY-SA 4.0
2018-05-25T19:33:46.033Z
This can be show by using 1) the reduction from streaming algorithms to communication protocols, and 2) reducing from the INDEX problem to the triangle-free problem.
Sam McGuire
CC BY-SA 4.0
2018-05-25T19:51:34.517Z
@SamMcGuire But isn't INDEX $\Omega(n)$? How do you get the quadratic lower bound?
Drew Brady
CC BY-SA 4.0
2018-05-25T20:05:33.133Z
You can reduce an $n$-bit instance of INDEX to a $O(\sqrt{n})$-node instance of triangle-free. See my answer for details.
Sam McGuire
<graph-theory><lower-bounds>
Lower bound for triangle-free graphs
Drew Brady
# Lower bound for triangle-free graphs

(Asked by: username_0 on 2018-05-25)

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?

**Tags:** graph-theory, lower-bounds

> **Comments:**
> **username_1**: This can be show by using 1) the reduction from streaming algorithms to communication protocols, and 2) reducing from the INDEX problem to the triangle-free problem.  
> **username_0**: @SamMcGuire But isn't INDEX $\Omega(n)$? How do you get the quadratic lower bound?  
> **username_1**: You can reduce an $n$-bit instance of INDEX to a $O(\sqrt{n})$-node instance of triangle-free. See my answer for details.  

---

## 1 answers

### Answer by username_1 on 2018-05-25. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: By the way, I think you mean to say $z_{P_L(k)}$ not $x_{P_L(k)}$.  

---

