All reports by Author Mathieu Laurière:

__
TR15-028
| 27th February 2015
__

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland#### Relative Discrepancy does not separate Information and Communication Complexity

__
TR13-015
| 18th January 2013
__

Iordanis Kerenidis, Mathieu Laurière, David Xiao#### New lower bounds for privacy in communication protocols

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

Iordanis Kerenidis, Mathieu Laurière, David Xiao

Communication complexity is a central model of computation introduced by Yao in 1979, where

two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed

function f with the least amount of communication. Recently people have revisited the question of the ...
more >>>