# Nondeterministic communication complexity

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

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