<p>In <a href="http://eccc.hpi-web.de/report/2012/171">a recent paper</a>, 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.</p>

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

CC BY-SA 3.0
2013-01-25T06:52:54.470Z
2013-01-25T06:52:54.470Z
Yonatan N
<p>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: </p>

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

<p>Also, is there any belief on the actual value of $\delta$?</p>

<p>[Razborov92] Alexander A. Razborov: On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2): 385-390 (1992) doi:<a href="http://dx.doi.org/10.1016/0304-3975(92)90260-M" rel="nofollow">10.1016/0304-3975(92)90260-M</a></p>

CC BY-SA 3.0
2013-01-25T03:36:51.513Z
Are you aware of the content of this recent paper? http://eccc.hpi-web.de/report/2012/171/ . The authors compute δ exactly as some constant near 0.4827 .
Yonatan N
CC BY-SA 3.0
2013-01-25T04:34:48.337Z
@Yonatan Make that an answer?
Yuval Filmus
CC BY-SA 3.0
2013-01-25T06:32:19.123Z
@YonatanN I'm not aware of this recent paper. Thanks so much for the pointer!
Dan
CC BY-SA 3.0
2013-01-25T07:35:00.100Z
Be careful, n+1 is for deterministic protocols and easy to prove, later papers are for randomized!
domotorp
<lower-bounds><communication-complexity>
Best communication complexity lower bound of disjointness
Dan
# Best communication complexity lower bound of disjointness

(Asked by: username_0 on 2013-01-25)

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](http://dx.doi.org/10.1016/0304-3975(92)90260-M)

**Tags:** lower-bounds, communication-complexity
> **Comments:**
> **username_1**: Are you aware of the content of this recent paper? http://eccc.hpi-web.de/report/2012/171/ . The authors compute δ exactly as some constant near 0.4827 .  
> **username_2**: @Yonatan Make that an answer?  
> **username_0**: @YonatanN I'm not aware of this recent paper. Thanks so much for the pointer!  
> **username_3**: Be careful, n+1 is for deterministic protocols and easy to prove, later papers are for randomized!  

---

## 1 answers

### Answer by username_1 on 2013-01-25. Score: 16 | Accepted answer

In [a recent paper](http://eccc.hpi-web.de/report/2012/171), 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.


---

