Trading Information Complexity for Error
Speaker
Yuval Dagan
Technion
Host
Akshay Degwekar, Pritish Kamath and Govind Ramnarayan
MIT
Abstract: We consider the standard two-party communication model. The central
problem studied in this article is how much one can save in
information complexity by allowing an error. Our major result is that
the epsilon-error randomized communication complexity of set
disjointness is n[C_DISJ - Theta(h(epsilon))] + o(n), where C_DISJ ?
0.4827 is the constant of set disjointness found by Braverman et al.
Joint work with Yuval Filmus, Hamed Hatami and Yaqiao Li.
problem studied in this article is how much one can save in
information complexity by allowing an error. Our major result is that
the epsilon-error randomized communication complexity of set
disjointness is n[C_DISJ - Theta(h(epsilon))] + o(n), where C_DISJ ?
0.4827 is the constant of set disjointness found by Braverman et al.
Joint work with Yuval Filmus, Hamed Hatami and Yaqiao Li.