All reports by Author Iordanis Kerenidis:

__
TR16-150
| 23rd September 2016
__

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez#### Streaming Communication Protocols

__
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

__
TR12-038
| 6th April 2012
__

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao#### Lower bounds on information complexity via zero-communication protocols and applications

__
TR06-087
| 25th July 2006
__

Iordanis Kerenidis, Ran Raz#### The one-way communication complexity of the Boolean Hidden Matching Problem

__
TR04-036
| 27th March 2004
__

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis#### Exponential Separation of Quantum and Classical One-Way Communication Complexity

__
TR02-059
| 9th August 2002
__

Iordanis Kerenidis, Ronald de Wolf#### Exponential Lower Bound for 2-Query Locally Decodable Codes

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>>

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 >>>

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition ... more >>>

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query

locally decodable codes. Goldreich et al. recently proved such bounds

for the special case of linear locally decodable codes.

Our proof shows that a 2-query locally decodable code can be decoded

with only 1 quantum query, and then ...
more >>>