I'm familiar with the fooling set technique to obtain lower bounds for communication complexity protocols. The most basic example is the equality function for which the diagonal matrix gives the fooling set of size $2^n$, because each 1-output needs to be in its own monochromatic rectangle. Also, a similar property seems to be true when looking at 0-outputs: If we have a cover of the 0-outputs by a set of monochromatic rectangles, then no rectangle can contain all 0-outputs of 2 (or more) rows. This implies that we get the same complexity for the NEQ (non-equality) problem.
However, I read that for non-deterministic algorithms, the complexity of NEQ is only $O(\log n)$. This is because we simply need to "guess" an index $i$ where the inputs of Alice and Bob differ, which takes $\log n$ bits and then use $1$ additional bit to encode if $i=0$ or $i=1$.
But the complexity of such a non-deterministic algorithms is lower-bounded by the log of the size of the smallest cover of the $0$-outputs, which would still be $\log(2^n)=n$ (by the above argument that each row in the matrix accounts for at least one rectangle in the cover).
Obviously, I'm missing something here, but I haven't figured out what it is...
