Chen, Victor ;
Grigorescu, Elena ;
de Wolf, Ronald
Efficient and ErrorCorrecting 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 \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 errorcorrecting data structure 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 \emph{length} (the number of bits in its representation), and queryanswering time, measured by the number of \emph{bitprobes} to the (possibly corrupted) representation. We obtain results for the following two data structure problems:
\begin{itemize}
\item (Membership) Store a subset $S$ of size at most $s$ from a universe of size $n$ such that membership queries can be answered efficiently, i.e., decide if a given element from the universe is in $S$. \\
We construct an errorcorrecting data structure for this problem with length nearly linear in $s\log n$ that answers membership queries with $O(1)$ bitprobes. This nearly matches the asymptotically optimal parameters for the noiseless case: length $O(s\log n)$ and one bitprobe, due to Buhrman, Miltersen, Radhakrishnan, and Venkatesh.
\item (Univariate polynomial evaluation) Store a univariate polynomial $g$ of degree $\deg(g)\leq s$ over the integers modulo $n$ such that evaluation queries can be answered efficiently, i.e., we can evaluate the output of $g$ on a given integer modulo $n$. \\
We construct an errorcorrecting data structure for this problem
with length nearly linear in $s\log n$ that answers evaluation queries
with $\polylog s\cdot\log^{1+o(1)}n$ bitprobes. This nearly matches
the parameters of the bestknown noiseless construction, due to Kedlaya and Umans.
\end{itemize}
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2010:2455,
author = {Victor Chen and Elena Grigorescu and Ronald de Wolf},
title = {{Efficient and ErrorCorrecting Data Structures for Membership and Polynomial Evaluation}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {203214},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2455},
URN = {urn:nbn:de:0030drops24558},
doi = {10.4230/LIPIcs.STACS.2010.2455},
annote = {Keywords: Data Structures, ErrorCorrecting Codes, Membership, Polynomial Evaluation}
}
2010
Keywords: 

Data Structures, ErrorCorrecting Codes, Membership, Polynomial Evaluation 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

2010 