Nondeterministic communication complexity

Question

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)$?

Answer 1

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$.