# Best communication complexity lower bound of disjointness

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

• 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 . – Yonatan N Jan 25 '13 at 3:36
• @Yonatan Make that an answer? – Yuval Filmus Jan 25 '13 at 4:34
• @YonatanN I'm not aware of this recent paper. Thanks so much for the pointer! – Danu Jan 25 '13 at 6:32
• Be careful, n+1 is for deterministic protocols and easy to prove, later papers are for randomized! – domotorp Jan 25 '13 at 7:35

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.