14
$\begingroup$

It is well known that no deterministic two-party protocol can solve disjointness problem (DISJ) on $n$-bit inputs without sending $n+1$ bits in the worst case (see, e.g., the book by Kushilevitz and Nisan). For bounded-error randomized protocols, a lower bound of $\delta n$, for some constant $\delta$, has also been shown in a seminal paper by Razborov [Razborov92]. My question is:

What is the best known explicit value of $\delta$ currently (both upper and lower bounds)?

Also, is there any belief on the actual value of $\delta$?

[Razborov92] Alexander A. Razborov: On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2): 385-390 (1992) doi:10.1016/0304-3975(92)90260-M

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ Are you aware of the content of this recent paper? eccc.hpi-web.de/report/2012/171 . The authors compute δ exactly as some constant near 0.4827 . $\endgroup$
    – Yonatan N
    Jan 25, 2013 at 3:36
  • 2
    $\begingroup$ @Yonatan Make that an answer? $\endgroup$
    – Yuval Filmus
    Jan 25, 2013 at 4:34
  • $\begingroup$ @YonatanN I'm not aware of this recent paper. Thanks so much for the pointer! $\endgroup$
    – Danu
    Jan 25, 2013 at 6:32
  • 4
    $\begingroup$ Be careful, n+1 is for deterministic protocols and easy to prove, later papers are for randomized! $\endgroup$
    – domotorp
    Jan 25, 2013 at 7:35

1 Answer 1

Reset to default
16
$\begingroup$

In a recent paper, Braverman, Garg, Pankratov, and Weinstein compute the value of $\delta$ to be exactly some constant around 0.4827, up to sublinear factors. This gives a tight bound on the communication complexity of disjointness.

The constant itself was found using a computer algebra system, and as far as I'm aware can't be expressed simply.

Improve this answer
$\endgroup$

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.