### 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 \emph{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 noise on the data structure, it answers \emph{all} queries correctly with high probability. Our model is the common generalization of an error-correcting data structure model...