Theory Seminar: Local List-Decoding with a Constant Number of Queries

קלים אפרנקו (אונ' ת"א)
יום רביעי, 15.12.2010, 12:20
חדר 337, בניין טאוב למדעי המחשב

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.

בחזרה לאינדקס האירועים