Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword.
Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed.
To prevent the ... more >>>

Suppose we have random sampling access to a huge object, such as a graph or a database.
Namely, we can observe the values of \emph{random} locations in the object, say random records in the database or random edges in the graph.
We cannot, however, query locations of our choice. Can ... more >>>