Lokalt Decodable Codes (LDC) tillåter en att avkoda någon särskild symbol för inmatningsmeddelandet genom att göra ett konstant antal frågor till ett kodord, även om en konstant bråkdel av kodordet skadas. I ett nyligen verk [Yek08] Yekhanin konstruerar en 3-query LDC med sub-exponentiell längd av storlek exp(exp( O( log n log log n ) )). Denna konstruktion kräver dock en gissning att det finns oändligt många Mersenne primer. I detta papper ger vi den första ovillkorliga konstant fråga LDC konstruktion med sub-exponentiell kodord längd. Dessutom minskar vår konstruktion kodordets längd. Vi ger en konstruktion av en 3-query LDC med kodordslängd exp(exp(O( В log n log log n))). Vår konstruktion kan också utökas till ett större antal frågor. Vi ger en 2 r-query LDC med längd exp(exp(O( r  på log n(log log n) r-1 ))).
Efremenko REF konstruerade en 3-query lokalt decodable kod för längd N = exp(exp( O( В log n log log n))) utan antagande.
3-query locally decodable codes of subexponential length
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}