Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-079 | 27th January 2010 17:15

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

RSS-Feed




Revision #1
Authors: Victor Chen, Elena Grigorescu, Ronald de Wolf
Accepted on: 27th January 2010 17:15
Downloads: 3417
Keywords: 


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.



Changes to previous version:

minor revisions.


Paper:

TR09-079 | 21st September 2009 09:41

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





TR09-079
Authors: Victor Chen, Elena Grigorescu, Ronald de Wolf
Publication: 22nd September 2009 19:50
Downloads: 5286
Keywords: 


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.



ISSN 1433-8092 | Imprint