Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR18-204 | 30th November 2018
Makrand Sinha, Ronald de Wolf

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Comments: 1

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

TR09-102 | 21st October 2009
Andrew Drucker, Ronald de Wolf

Quantum Proofs for Classical Theorems

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

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

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

ISSN 1433-8092 | Imprint