<p>Communication with partial information is the topic of Chapter 4.7 in the Kushilevitz-Nisan book, building mainly on work by Orlitsky. There they are concerned with the number of rounds in a deterministic protocol but I would guess that the nondeterministic bounds were also known.</p>

CC BY-SA 4.0
2023-03-26T19:01:25.313Z
Thanks! These results certainly have similar flavor, but they are not exactly the same. The main difference is that in Orlitsky's setting, Bob wants to learn Alice's input, while in my setting, they merely want to know if their inputs are equal. This makes my problem somewhat easier.
Or Meir
CC BY-SA 4.0
2023-03-25T05:35:29.257Z
2023-03-25T05:35:29.257Z
domotorp
<p>I came upon a nice observation in communication complexity, and I was wondering if it was already known.</p>
<p>Consider the following variant of the equality problem: There is a fixed graph <span class="math-container">$G$</span> that is known in advance to both Alice and Bob. The players each get a vertex of <span class="math-container">$G$</span>, and they need to decide whether their vertices are equal or not. Now, the point is that the players are promised that if their vertices are not equal, then they are neighbors in <span class="math-container">$G$</span>. The standard equality problem corresponds to the case where <span class="math-container">$G$</span> is the complete graph.</p>
<p>It is not hard to prove that if the chromatic number of <span class="math-container">$G$</span> is <span class="math-container">$\chi(G)$</span>, then the nondeterministic communication complexity of this problem is exactly <span class="math-container">$\log(\chi(G)) + \Theta(1)$</span>, and the co-nondeterministic complexity is exactly <span class="math-container">$\log\log(\chi(G)) + \Theta(1)$</span>.</p>
<p>Is this result published anywhere?</p>

<communication-complexity>
Communication complexity of equality on graphs
Or Meir
# Communication complexity of equality on graphs

(Asked by: username_0 on 2023-03-24)

I came upon a nice observation in communication complexity, and I was wondering if it was already known.

Consider the following variant of the equality problem: There is a fixed graph $G$ that is known in advance to both Alice and Bob. The players each get a vertex of $G$, and they need to decide whether their vertices are equal or not. Now, the point is that the players are promised that if their vertices are not equal, then they are neighbors in $G$. The standard equality problem corresponds to the case where $G$ is the complete graph.

It is not hard to prove that if the chromatic number of $G$ is $\chi(G)$, then the nondeterministic communication complexity of this problem is exactly $\log(\chi(G)) + \Theta(1)$, and the co-nondeterministic complexity is exactly $\log\log(\chi(G)) + \Theta(1)$.

Is this result published anywhere?

**Tags:** communication-complexity


---

## 1 answers

### Answer by username_1 on 2023-03-25. Score: 1

Communication with partial information is the topic of Chapter 4.7 in the Kushilevitz-Nisan book, building mainly on work by Orlitsky. There they are concerned with the number of rounds in a deterministic protocol but I would guess that the nondeterministic bounds were also known.

> **Comments:**
> **username_0**: Thanks! These results certainly have similar flavor, but they are not exactly the same. The main difference is that in Orlitsky's setting, Bob wants to learn Alice's input, while in my setting, they merely want to know if their inputs are equal. This makes my problem somewhat easier.  

---

