Yuval Dagan: Trading Information Complexity for Error

Thursday, September 28, 2017 - 3:00pm to 4:00pm
Location: 
32-G575
Speaker: 
Yuval Dagan
Biography: 
Technion

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.