2026-08-11T15:04:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1802 2024-03-06T10:33:11Z ddc:004 open_access

Error-Correcting Data Structures de Wolf, Ronald Data structures Error-correcting codes Locally decodable codes Membership We study data structures in the presence of adversarial noise. We want to encode a given object in a succinct data structure that enables us to efficiently answer specific queries about the object, even if the data structure has been corrupted by a constant fraction of errors. This new model is the common generalization of (static) data structures and locally decodable error-correcting codes. The main issue is the tradeoff between the space used by the data structure and the time (number of probes) needed to answer a query about the encoded object. We prove a number of upper and lower bounds on various natural error-correcting data structure problems. In particular, we show that the optimal length of error-correcting data structures for the {\sc Membership} problem (where we want to store subsets of size $s$ from a universe of size $n$) is closely related to the optimal length of locally decodable codes for $s$-bit strings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ronald de Wolf 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1802 urn:nbn:de:0030-drops-18024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1802 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode