Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Abstract : 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 noise on the data structure, it answers all queries correctly with high probability. Our model is the common generalization of a model proposed recently by de Wolf and the notion of "relaxed locally decodable codes" developed in the PCP literature. We measure the efficiency of a data structure in terms of its length, measured by the number of bits in its representation, and query-answering time, measured by the number of bit-probes to the (possibly corrupted) representation. In this work, we study two data structure problems: membership and polynomial evaluation. We show that these two problems have constructions that are simultaneously efficient and error-correcting.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.203-214, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455571
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 16:34:04
Dernière modification le : mercredi 20 décembre 2017 - 17:42:07
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:01:16

Fichier

chen.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455571, version 1

Collections

Citation

Victor Chen, Elena Grigorescu, Ronald De Wolf. Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.203-214, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455571〉

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

55