<p>Yes, there is a large 0-fooling set.
It is enough to prove this for $r=2$, as we can add (the same) $r-2$ independent vertices to all graphs in our construction.
For $r=2$, take every graph that has exactly ${n\choose 2}/2$ edges.
Everyone will fool around with its complement.</p>

CC BY-SA 3.0
2015-04-01T12:51:06.050Z
Thanks, that's great!  This 0-fooling set gives $N^0(\text{IS}_{n,r}) \ge \Omega(n^2)$ which is essentially the best possible.
András Salamon
CC BY-SA 3.0
2015-03-31T22:55:56.343Z
2015-03-31T22:55:56.343Z
domotorp
<p>Consider the following communication game.</p>

<h2>Independent Set game</h2>

<p>Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$.
Alice receives a set $X$ of edges, each edge being a pair of distinct vertices from $[n]$, and Bob receives a set $Y$ of edges.
Alice and Bob must communicate to determine whether the graph $([n],X \cup Y)$ contains an independent set with $r$ vertices.
Let IS$_{n,r}(X,Y) = 1$ if there is such a set, and IS$_{n,r}(X,Y) = 0$ otherwise.</p>

<p>There is a simple nondeterministic protocol to confirm that IS$_{n,r}(X,Y) = 1$; Alice nondeterministically chooses an $r$-vertex set $I$ that forms an independent set in her graph $([n],X)$ and sends Bob a description of this set using at most $r(1+\log n)$ bits.
Bob responds with 1 if $I$ is an independent set in $([n],Y)$ also; otherwise he responds with 0.
On the other hand, there is a fooling set of pairs of sets $(V,V)$ such that $([n],V)$ is a graph formed by $r$ disconnected vertices adjoined to a complete graph with $n-r$ vertices.
This 1-fooling set contains $\binom{n}{r}$ such fooling pairs, so the nondeterministic communication complexity of $\text{IS}_{n,r}$ is at least $\Omega(r\log n)$.
It follows that the simple protocol is optimal up to a small constant factor.</p>

<p>My question is:</p>

<blockquote>
  <p>Is there a large 0-fooling set for IS$_{n,r}$?</p>
</blockquote>

<p>If not, is there an efficient deterministic protocol?</p>

<p>I would also be interested in pointers to the literature if this problem is known.
The closest I have found is the Clique vs. Independent Set game of Yannakakis but this did not seem useful here.</p>

<cc.complexity-theory><lower-bounds><communication-complexity>
Communication complexity of Independent Set game?
András Salamon
# Communication complexity of Independent Set game?

(Asked by: username_0 on 2015-03-31)

Consider the following communication game.

## Independent Set game

Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$.
Alice receives a set $X$ of edges, each edge being a pair of distinct vertices from $[n]$, and Bob receives a set $Y$ of edges.
Alice and Bob must communicate to determine whether the graph $([n],X \cup Y)$ contains an independent set with $r$ vertices.
Let IS$\_{n,r}(X,Y) = 1$ if there is such a set, and IS$\_{n,r}(X,Y) = 0$ otherwise.

There is a simple nondeterministic protocol to confirm that IS$\_{n,r}(X,Y) = 1$; Alice nondeterministically chooses an $r$-vertex set $I$ that forms an independent set in her graph $([n],X)$ and sends Bob a description of this set using at most $r(1+\log n)$ bits.
Bob responds with 1 if $I$ is an independent set in $([n],Y)$ also; otherwise he responds with 0.
On the other hand, there is a fooling set of pairs of sets $(V,V)$ such that $([n],V)$ is a graph formed by $r$ disconnected vertices adjoined to a complete graph with $n-r$ vertices.
This 1-fooling set contains $\binom{n}{r}$ such fooling pairs, so the nondeterministic communication complexity of $\text{IS}\_{n,r}$ is at least $\Omega(r\log n)$.
It follows that the simple protocol is optimal up to a small constant factor.

My question is:

> Is there a large 0-fooling set for IS$\_{n,r}$?

If not, is there an efficient deterministic protocol?

I would also be interested in pointers to the literature if this problem is known.
The closest I have found is the Clique vs. Independent Set game of Yannakakis but this did not seem useful here.

**Tags:** cc.complexity-theory, lower-bounds, communication-complexity


---

## 1 answers

### Answer by username_1 on 2015-03-31. Score: 3 | Accepted answer

Yes, there is a large 0-fooling set.
It is enough to prove this for $r=2$, as we can add (the same) $r-2$ independent vertices to all graphs in our construction.
For $r=2$, take every graph that has exactly ${n\choose 2}/2$ edges.
Everyone will fool around with its complement.

> **Comments:**
> **username_0**: Thanks, that's great!  This 0-fooling set gives $N^0(\text{IS}_{n,r}) \ge \Omega(n^2)$ which is essentially the best possible.  

---

