10
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ You mean the opposite (small randomized, but large deterministic)? $\endgroup$
    – Noam
    Feb 6, 2014 at 20:35
  • $\begingroup$ 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? $\endgroup$
    – withhighprob
    Feb 7, 2014 at 8:02

1 Answer 1

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks a lot. That answers perfectly what I want to know. $\endgroup$
    – withhighprob
    Feb 7, 2014 at 19:30
  • $\begingroup$ Sorry, I will do that. $\endgroup$
    – withhighprob
    Mar 28, 2014 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.