1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Or Meir
    Commented Mar 26, 2023 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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