<p>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)$.  </p>

<p>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.</p>

<p>See: <a href="http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf">http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf</a> </p>

CC BY-SA 3.0
2014-03-28T14:59:48.317Z
Sorry, I will do that.
withhighprob
CC BY-SA 3.0
2014-02-07T19:30:14.973Z
Thanks a lot. That answers perfectly what I want to know.
withhighprob
CC BY-SA 3.0
2014-02-07T16:50:24.567Z
2014-02-07T17:33:04.167Z
2014-02-07T17:33:04.167Z
Noam
<p>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.</p>

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

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

<p>Any help is appreciated. </p>

CC BY-SA 3.0
2014-02-06T20:35:10.663Z
You mean the opposite (small randomized, but large deterministic)?
Noam
CC BY-SA 3.0
2014-02-07T08:02:28.867Z
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
<communication-complexity>
Zero error randomized communication complexity vs deterministic communication complexity
withhighprob
# Zero error randomized communication complexity vs deterministic communication complexity

(Asked by: username_0 on 2014-02-06)

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.

**Tags:** communication-complexity
> **Comments:**
> **username_1**: You mean the opposite (small randomized, but large deterministic)?  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_1 on 2014-02-07. Score: 13 | Accepted answer

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.

See: <http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf>

> **Comments:**
> **username_0**: Thanks a lot. That answers perfectly what I want to know.  
> **username_0**: Sorry, I will do that.  

---

