# Zero error randomized communication complexity vs deterministic communication complexity

It is known that for $\Theta(1)$ error the worst case definition of randomized communication complexity and average case definition are equivalent. But when the error is $0$, the worst case randomized communication complexity is same as deterministic communication complexity.

Is any function known to have super-constant deterministic communication complexity but constant zero error randomized communication complexity?

More generally, what is a witness function that separates deterministic communication complexity and zero-error randomized communication complexity?

Any help is appreciated.

• You mean the opposite (small randomized, but large deterministic)? – Noam Feb 6 '14 at 20:35
• Yes, extremely sorry for that mess. I want constant zero-error randomized communication complexity but super constant deterministic communication complexity. I was looking t the problem of $k$-set disjointness. As $R_0(f)=O(max\{R^1(f), R^1(\text{not }f)\})$ and Hastad-Wigderson protocol already gives a one-sided protocol for $k$-set disjointness of cost $O(k)$ the problem boils down to proving a constant cost randomized bounded-error one-sided upper bound for not-k-set-disjointness. Is there already a result? – withhighprob Feb 7 '14 at 8:02

Indeed, for distjointness of sets of size $\log(n)$ out of $n$ items, it is known that the $0$-error randomized communication complexity is $\Theta(\log n)$, while the deterministic complexity is $\Theta(\log^2 n)$.
Recall that there can be at most a quadratic gap since the $0$-error randomized complexity is bounded from below by the non-deterministic and co-non-deterministic complexities.