All reports by Author Ronald de Wolf:

__
TR06-086
| 25th July 2006
__

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf#### Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

__
TR04-045
| 15th April 2004
__

Hartmut Klauck, Robert Spalek, Ronald de Wolf#### Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

__
TR02-059
| 9th August 2002
__

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

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

Hartmut Klauck, Robert Spalek, Ronald de Wolf

A strong direct product theorem says that if we want to compute

k independent instances of a function, using less than k times

the resources needed for one instance, then our overall success

probability will be exponentially small in k.

We establish such theorems for the classical as well as ...
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 >>>