locally decodable codes

E831746

coding theory concept error-correcting code

Locally decodable codes are error-correcting codes that allow the recovery of any specific symbol of the original message by querying only a small number of positions in a possibly corrupted codeword.

Try in SPARQL Jump to: Statements Referenced by

Statements (52)

Predicate	Object
instanceOf	coding theory concept ⓘ error-correcting code ⓘ
allows	decoding of individual message symbols ⓘ querying only a few codeword positions ⓘ
application	complexity theory ⓘ fault-tolerant data storage ⓘ locally decodable data structures ⓘ private information retrieval schemes ⓘ
contrastWith	global decoding of error-correcting codes ⓘ locally testable codes ⓘ
decoderAccessPattern	adaptive queries ⓘ non-adaptive queries ⓘ
decoderType	randomized local decoder ⓘ
definition	codes that allow recovery of any specific symbol of the original message by querying only a small number of positions of a possibly corrupted codeword ⓘ
field	coding theory ⓘ information theory ⓘ theoretical computer science ⓘ
goal	recover a specific message symbol with high probability ⓘ tolerate adversarial errors ⓘ use few queries to the codeword ⓘ
hasProperty	error resilience ⓘ local decodability ⓘ randomized decoding ⓘ sublinear-time decoding ⓘ tolerates a constant fraction of errors ⓘ
hasVariant	2-query locally decodable codes ⓘ 3-query locally decodable codes ⓘ binary locally decodable codes ⓘ linear locally decodable codes ⓘ locally decodable codes over large alphabets ⓘ q-query locally decodable codes ⓘ smooth locally decodable codes ⓘ
lowerBoundProperty	2-query locally decodable codes require exponential length over binary alphabets ⓘ
notableResearcher	Avi Wigderson NERFINISHED ⓘ Kobbi Nissim NERFINISHED ⓘ Madhu Sudan NERFINISHED ⓘ Oded Goldreich NERFINISHED ⓘ
parameter	alphabet size ⓘ code length ⓘ decoding success probability ⓘ error tolerance ⓘ query complexity ⓘ rate ⓘ
relatedTo	data structures ⓘ hardness of approximation ⓘ locally testable codes ⓘ private information retrieval ⓘ probabilistically checkable proofs ⓘ sublinear algorithms ⓘ
researchedSince	1990s ⓘ
typicalQueryComplexity	constant number of queries GENERATED ⓘ polylogarithmic number of queries GENERATED ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Moni Naor → researchArea → locally decodable codes ⓘ