Computer Science – Data Structures and Algorithms
Scientific paper
2009-09-21
Computer Science
Data Structures and Algorithms
An abridged version of this paper appears in STACS 2010
Scientific paper
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.
Chen Victor
Grigorescu Elena
Wolf Ronald de
No associations
LandOfFree
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-432070