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…