9 citations · 15 across the 4 of their papers we have counts for
4 papers
Two new results about quantum exact learning
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +2
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a -Fourier-sparse -bit Boolean function from …
Optimal quantum query bounds for almost all Boolean functions
Andris Ambainis, Arturs Backurs, Juris Smotrovs +1
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of…
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation
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…
Error-Correcting Data Structures
Ronald de Wolf
We study data structures in the presence of adversarial noise. We want to encode a given object in a succinct data structure that enables us to efficiently answer specific queries…