All reports by Author Ronald de Wolf:

__
TR21-113
| 25th July 2021
__

Nikhil Mande, Ronald de Wolf#### Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

__
TR18-204
| 30th November 2018
__

Makrand Sinha, Ronald de Wolf#### Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Comments: 1

__
TR09-102
| 21st October 2009
__

Andrew Drucker, Ronald de Wolf#### Quantum Proofs for Classical Theorems

__
TR09-079
| 21st September 2009
__

Victor Chen, Elena Grigorescu, Ronald de Wolf#### Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

Nikhil Mande, Ronald de Wolf

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models.

The following are our results in the randomized model:

1) We give a general technique to convert ... more >>>

Makrand Sinha, Ronald de Wolf

Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total

Boolean function, the sink function, that has polynomial approximate rank and

polynomial randomized communication complexity. This gives an exponential

separation between randomized communication complexity and logarithm of the

approximate rank, refuting the log-approximate-rank conjecture. We show that ...
more >>>

Andrew Drucker, Ronald de Wolf

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

more >>>Victor Chen, Elena Grigorescu, Ronald de Wolf

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the

decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ...
more >>>