Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: Local List-Decoding with a Constant Number of Queries
event speaker icon
Klim Efremenko (Tel-Aviv University)
event date icon
Wednesday, 15.12.2010, 12:20
event location icon
Room 337-8 Taub Bld.
Recently there was constructed locally-decodable codes of sub-exponential length. This result showed that these codes can handle up to one third fraction of errors. In this talk we show that the same codes can be locally unique-decoded from error rate upto half and locally list-decoded from error rate $1-\alpha$ for any $\alpha>0$, with only a constant number of queries and a constant alphabet size. This gives the first sub-exponential codes that can be locally list-decoded with a constant number of queries. We also will show a generic, simple way to amplify the error-tolerance of any locally decodable code.
[Back to the index of events]