5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sam McGuire May 25 '18 at 19:33
  • $\begingroup$ @SamMcGuire But isn't INDEX $\Omega(n)$? How do you get the quadratic lower bound? $\endgroup$ – Drew Brady May 25 '18 at 19:51
  • $\begingroup$ You can reduce an $n$-bit instance of INDEX to a $O(\sqrt{n})$-node instance of triangle-free. See my answer for details. $\endgroup$ – Sam McGuire May 25 '18 at 20:05
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ By the way, I think you mean to say $z_{P_L(k)}$ not $x_{P_L(k)}$. $\endgroup$ – Drew Brady May 25 '18 at 21:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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