$NotTooManyP^{cc}$ class in communication complexity

Question

Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication.

Class $NP^{cc}$ is class of languages admitting nondeterministic communication protocol with polylog size witness.

Class $FewP^{cc}$ is class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polylog correct witnesses.

It was proven that $FewP^{cc} = P^{cc}$ [1]. My question is about what happens if we allow not too many correct witnesses instead of few.

Let class $NotTooManyP^{cc}$ be class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polynomial correct witnesses. Is this class different from $P^{cc}$? If yes, how much weaker is this class then $NP^{cc}$?

Answer 1

When the inputs are the indicator functions, set non-disjointness is in NP^cc with witnesses
from {0,1,2,3,...,n-2,n-1} $\big(\hspace{-0.04 in}$so in particular is in NotTooManyP^cc$\hspace{-0.03 in}\big)$, ​ but by this paper,
the coUSBP (and thus also P) communication complexity of that problem is $\Theta$(n).
By padding, that means we leave coUSBP^cc $\big(\hspace{-0.04 in}$and thus also P^cc$\hspace{-0.03 in}\big)$ ​ as soon
as the number of witnesses is no longer polylogarithmically-bounded.

Also, for all functions ​ f : {0,1,2,3,...} $\to$ (0,1] , ​ if the version with at most
n^f(n) correct witnesses equals NP^cc then f has a positive lower bound.


Proof:

Let f be any function from {0,1,2,3,...} to (0,1] such that the problem at
the start of this answer can be solved with at most n^f(n) correct witnesses.
Let ​ g : {0,1,2,3,...} $\to$ {0,1,2,3,...} ​ be given by
g(0) = 0 = g(1) ​ and otherwise ​ g(n) = (log(n))^1/(f(n)) ​ .
g(0) = 0 ​ and ​ g(1) = 0 < 1 ​ and ​ for all other inputs n,
g(n) = (log(n))^1/(f(n)) < n^1/(f(n)) ≤ n^1/1 = n¹ = n ​ .
Accordingly, consider the problem ​ ​ non-disjointness of subsets of ​ {0,1,2,3,...,(g(n))-2,(g(n))-1} ​ whose inputs are padded indicator functions.
By removing the padding, that problem can be solved with at most (g(n))^f(n) correct witnesses.
For all integers n such that ​ 1 < n , ​ (g(n))^f(n) = $\big(\hspace{-0.05 in}$(log(n))^1/(f(n))$\hspace{-0.03 in}\big)^{\hspace{.02 in}f\hspace{.02 in}(n)}$ = (log(n))^{(1/(f(n)))$\cdot$f(n)} = (log(n))¹ .
Thus the problem is in FewP^cc, so by the result you mentioned, it's also in P^cc.
By the communication lower bound in this answer's starting sentence, that means g is
at most polylogarithmic, so 1/(f(n)) is bounded above, so f has a positive lower bound.

I'm not aware of any other results about limited-ambiguity versions of NP^cc,
although with inputs as in the rest of this answer, (paddings of, if necessary) the problems
" ​ Does the intersection have at least _ elements? ​ "
seem like natural candidates for separating those classes.

$\big(\hspace{-0.04 in}$On the other hand, I wasn't even aware of ​ unambiguousP^cc = P^cc ,
and still know neither a proof of that nor a reference for that.$\hspace{-0.03 in}\big)$