<p>The definition that uses a proof system works. The way to think about it is as if the prover sees the inputs of both parties and sends the same proof to both parties. Then, each party decides whether to accept or reject independently. If both of them choose to accept, then the input is accepted, otherwise it is rejected.</p>
<p>Note that in this definition, Alice and Bob do not communicate. Indeed, this is unnecessary: the prover can send them, as part of the proof, whatever messages they would have wanted to send each other.</p>
<p>Define the complexity of such a proof system to be the length of the longest proof that the prover uses. Using this definition, <span class="math-container">$N^1(f)$</span> is exactly the smallest complexity of a proof system for <span class="math-container">$f$</span> (though you might need to replace <span class="math-container">$\log C^1(f)$</span> with <span class="math-container">$\lceil \log C^1(f) \rceil$</span>). To see it:</p>
<ul>
<li><p>If you have a proof system, you can convert into a rectangle cover as follows: for every possible proof <span class="math-container">$w$</span> of the prover, consider the set <span class="math-container">$R_w$</span> of inputs <span class="math-container">$(x,y)$</span> on which both Alice and Bob accept <span class="math-container">$w$</span>. It is not hard to see that the sets <span class="math-container">$R_w$</span> are rectangles and that together they cover all the <span class="math-container">$1$</span>-inputs.</p>
</li>
<li><p>If you have a cover of the <span class="math-container">$1$</span>-inputs by rectangles, you can convert it into a proof system as follows: when the prover sees a <span class="math-container">$1$</span>-input <span class="math-container">$(x,y)$</span>, it sends as a proof the name of a rectangle <span class="math-container">$R = A \times B$</span> in the cover that contains <span class="math-container">$(x,y)$</span>. Then, Alice and Bob check that <span class="math-container">$x\in A$</span> and <span class="math-container">$y \in B$</span> respectively. It is not hard to see that if both Alice and Bob accept then it must be the case that <span class="math-container">$f(x,y)=1$</span>.</p>
</li>
</ul>

CC BY-SA 4.0
2022-02-12T21:11:17.200Z
2022-02-12T21:11:17.200Z
Or Meir
<p>Let <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> be finite sets and <span class="math-container">$f : X \times Y \to \{0,1\}$</span>.  I am confused about the definition of the deterministic communication complexity of <span class="math-container">$f$</span>, denoted <span class="math-container">$N^1(f)$</span>, or rather about the motivation for the definition.  The definition that I have seen is that <span class="math-container">$N^1(f)$</span> is <span class="math-container">$N^1(f) = \log C^1(f)$</span> where <span class="math-container">$C^1(f)$</span> is the minimal number of monochromatic rectangles needed to cover the <span class="math-container">$1$</span>-region of the matrix representation of <span class="math-container">$f$</span>.</p>
<p>I imagine this definition is really a result hidden in a definition and I am trying to work that out - what follows has a few subquestions, but I thought it was fitting to ask all of this as one question since I think a few words from a pro will set me straight with all of this confusion.</p>
<p><strong>Nondeterministic communication protocols:</strong></p>
<p>We could define a nondeterministic communication protocol in the same way as a usual communication protocol, but allow the internal nodes to be labeled by multiple possible functions - so a single nonleaf node <span class="math-container">$v$</span> will be labeled by functions <span class="math-container">$a_v^1,...,a_v^{n_v} : X \to \{0,1\}$</span> (if it is an Alice node) or <span class="math-container">$b_v^1,...,b_v^{n_v} : Y \to \{0,1\}$</span> (if it is a Bob node).  We say such a nondeterministic protocol computes <span class="math-container">$f$</span> if for all <span class="math-container">$(x,y) \in X \times Y$</span> we have <span class="math-container">$f(x,y) =1$</span> if and only if there is some possible choice of vertex function for each <span class="math-container">$v$</span>, from <span class="math-container">$a_v^i$</span> or <span class="math-container">$b_v^j$</span> given, such that with all those choices, the corresponding deterministic protocol evaluates to 1 on <span class="math-container">$(x,y)$</span>.  We then can define the complexity of <span class="math-container">$f$</span> with respect to this model as the minimum depth of such a protocol that computes <span class="math-container">$f$</span> - for a second let me call this complexity <span class="math-container">$\kappa(f)$</span>.</p>
<p>If I said that definition correctly, we should have <span class="math-container">$\kappa(f) = N^1(f)$</span>.  Is this the case?  In particular, such a nondeterministic protocol should yield a monochromatic covering of the 1-region of the matrix representing <span class="math-container">$f$</span>.  Well that part I can see, namely we have the covering that takes the union over all branches of the computation of the union overall leaves labeled 1 of the corresponding rectangle.  Or for the sake of having notation <span class="math-container">$\cup_B \cup_v R_v^B$</span> where <span class="math-container">$B$</span> is a possible branch and <span class="math-container">$v$</span> is a leaf labeled <span class="math-container">$1$</span>.  Well I don't exactly see how that helps (that could be a huge cover since we have no control over the number of branches).  Did I mess up the definition of the model?</p>
<p><strong>Another try - nondeterminism as a proof system:</strong></p>
<p>Well, this is supposed to work also.  I suppose I want to know modify the model to allow <span class="math-container">$a_v : X \times A \to \{0,1\}$</span> where the element of <span class="math-container">$A$</span> is some proof a verifier gives us.  I'm a bit confused on the details of this model though - should Alice and Bob both have the same set <span class="math-container">$A$</span> or should Bob have a different set so his functions look like <span class="math-container">$b_v : Y \times B \to \{0,1\}$</span>?  Does it matter what <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are (i.e., <span class="math-container">$\{0,1\}$</span> or <span class="math-container">$\{0,1\}^*$</span>)?  We then can define the complexity with respect to this model - is this again <span class="math-container">$N^1(f)$</span>?</p>

<reference-request><communication-complexity>
Nondeterministic communication complexity
user101010
# Nondeterministic communication complexity

(Asked by: username_0 on 2022-02-12)

Let $X$ and $Y$ be finite sets and $f : X \times Y \to \{0,1\}$. I am confused about the definition of the deterministic communication complexity of $f$, denoted $N^1(f)$, or rather about the motivation for the definition. The definition that I have seen is that $N^1(f)$ is $N^1(f) = \log C^1(f)$ where $C^1(f)$ is the minimal number of monochromatic rectangles needed to cover the $1$-region of the matrix representation of $f$.

I imagine this definition is really a result hidden in a definition and I am trying to work that out - what follows has a few subquestions, but I thought it was fitting to ask all of this as one question since I think a few words from a pro will set me straight with all of this confusion.

**Nondeterministic communication protocols:**

We could define a nondeterministic communication protocol in the same way as a usual communication protocol, but allow the internal nodes to be labeled by multiple possible functions - so a single nonleaf node $v$ will be labeled by functions $a\_v^1,...,a\_v^{n\_v} : X \to \{0,1\}$ (if it is an Alice node) or $b\_v^1,...,b\_v^{n\_v} : Y \to \{0,1\}$ (if it is a Bob node). We say such a nondeterministic protocol computes $f$ if for all $(x,y) \in X \times Y$ we have $f(x,y) =1$ if and only if there is some possible choice of vertex function for each $v$, from $a\_v^i$ or $b\_v^j$ given, such that with all those choices, the corresponding deterministic protocol evaluates to 1 on $(x,y)$. We then can define the complexity of $f$ with respect to this model as the minimum depth of such a protocol that computes $f$ - for a second let me call this complexity $\kappa(f)$.

If I said that definition correctly, we should have $\kappa(f) = N^1(f)$. Is this the case? In particular, such a nondeterministic protocol should yield a monochromatic covering of the 1-region of the matrix representing $f$. Well that part I can see, namely we have the covering that takes the union over all branches of the computation of the union overall leaves labeled 1 of the corresponding rectangle. Or for the sake of having notation $\cup\_B \cup\_v R\_v^B$ where $B$ is a possible branch and $v$ is a leaf labeled $1$. Well I don't exactly see how that helps (that could be a huge cover since we have no control over the number of branches). Did I mess up the definition of the model?

**Another try - nondeterminism as a proof system:**

Well, this is supposed to work also. I suppose I want to know modify the model to allow $a\_v : X \times A \to \{0,1\}$ where the element of $A$ is some proof a verifier gives us. I'm a bit confused on the details of this model though - should Alice and Bob both have the same set $A$ or should Bob have a different set so his functions look like $b\_v : Y \times B \to \{0,1\}$? Does it matter what $A$ and $B$ are (i.e., $\{0,1\}$ or $\{0,1\}^\*$)? We then can define the complexity with respect to this model - is this again $N^1(f)$?

**Tags:** reference-request, communication-complexity


---

## 1 answers

### Answer by username_1 on 2022-02-12. Score: 2

The definition that uses a proof system works. The way to think about it is as if the prover sees the inputs of both parties and sends the same proof to both parties. Then, each party decides whether to accept or reject independently. If both of them choose to accept, then the input is accepted, otherwise it is rejected.

Note that in this definition, Alice and Bob do not communicate. Indeed, this is unnecessary: the prover can send them, as part of the proof, whatever messages they would have wanted to send each other.

Define the complexity of such a proof system to be the length of the longest proof that the prover uses. Using this definition, $N^1(f)$ is exactly the smallest complexity of a proof system for $f$ (though you might need to replace $\log C^1(f)$ with $\lceil \log C^1(f) \rceil$). To see it:

* If you have a proof system, you can convert into a rectangle cover as follows: for every possible proof $w$ of the prover, consider the set $R\_w$ of inputs $(x,y)$ on which both Alice and Bob accept $w$. It is not hard to see that the sets $R\_w$ are rectangles and that together they cover all the $1$-inputs.
* If you have a cover of the $1$-inputs by rectangles, you can convert it into a proof system as follows: when the prover sees a $1$-input $(x,y)$, it sends as a proof the name of a rectangle $R = A \times B$ in the cover that contains $(x,y)$. Then, Alice and Bob check that $x\in A$ and $y \in B$ respectively. It is not hard to see that if both Alice and Bob accept then it must be the case that $f(x,y)=1$.


---

