Tite Probabilistic Communication Complexity of Set Intersection (Preliminary Version)
- 1 June 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We show that the probabilistic (bounded error) communication complexity of set intersection is θ(n). This proves a conjecture of Babai, Frankl and Simon. We therefore have an example of a NP-Complete language (in the context of Communication Complexity) that has no asymptotic speed up for bounded error probabilism.Keywords
This publication has 0 references indexed in Scilit: