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

$\endgroup$
  • 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 '13 at 3:36
  • 2
    $\begingroup$ @Yonatan Make that an answer? $\endgroup$ – Yuval Filmus Jan 25 '13 at 4:34
  • $\begingroup$ @YonatanN I'm not aware of this recent paper. Thanks so much for the pointer! $\endgroup$ – Danu Jan 25 '13 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 '13 at 7:35
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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