<p>What are the strengths and limitations of discrepancy method, corruption bound and general discrepancy method? Why is the corruption bound better at characterizing complexity of disjointness and inner product even upto multiplicative factors? Any fundamental reasons on why one should pick one versus the other in classical communication complexity?</p>

CC BY-SA 3.0
2014-12-16T01:32:44.067Z
Do you want any other reason except that the discrepancy of the set disjointness matrix is $\Omega(n^{-1})$?
Sasho Nikolov
CC BY-SA 3.0
2014-12-16T02:24:46.250Z
Yes.. sorry if my question is confusing. And actually the other part is why does corruption and general disc work where disc fails or not give fully linear bound (with $1$ as constant multiplicative factor) like in inner product?
Turbo
CC BY-SA 3.0
2014-12-16T09:21:35.953Z
Doesn't the partition bound subsume these ?
Suresh Venkat
CC BY-SA 3.0
2014-12-16T09:25:06.637Z
@SureshVenkat can you please provide a reference? I am not sure about partition bound.
Turbo
CC BY-SA 3.0
2014-12-17T16:28:10.487Z
The partition bound subsumes all other bounds except those from information theory. http://arxiv.org/pdf/0910.4266v2.pdf. The internal information theory subsumes all the bounds except the partition bound http://arxiv.org/abs/1204.1505. The external information complexity is same as communication complexity up to a log factor. (I forget the reference for this one, but I think you get deduce it using the technique from http://www.boazbarak.org/Papers/directsum.pdf)
pyao
<communication-complexity>
Limitations of techniques in communication complexity
Turbo
# Limitations of techniques in communication complexity

(Asked by: username_0 on 2014-12-15)

What are the strengths and limitations of discrepancy method, corruption bound and general discrepancy method? Why is the corruption bound better at characterizing complexity of disjointness and inner product even upto multiplicative factors? Any fundamental reasons on why one should pick one versus the other in classical communication complexity?

**Tags:** communication-complexity

> **Comments:**
> **username_1**: Do you want any other reason except that the discrepancy of the set disjointness matrix is $\Omega(n^{-1})$?  
> **username_0**: Yes.. sorry if my question is confusing. And actually the other part is why does corruption and general disc work where disc fails or not give fully linear bound (with $1$ as constant multiplicative factor) like in inner product?  
> **username_2**: Doesn't the partition bound subsume these ?  
> **username_0**: @SureshVenkat can you please provide a reference? I am not sure about partition bound.  
> **username_3**: The partition bound subsumes all other bounds except those from information theory. http://arxiv.org/pdf/0910.4266v2.pdf. The internal information theory subsumes all the bounds except the partition bound http://arxiv.org/abs/1204.1505. The external information complexity is same as communication complexity up to a log factor. (I forget the reference for this one, but I think you get deduce it using the technique from http://www.boazbarak.org/Papers/directsum.pdf)  

---

## 0 answers

