Vi utformar de första effektiva algoritmer och bevisa nya kombinatoriska gränser för lista avkodning tensorer produkter av koder och interleaded koder. (1) Vi visar att för varje kod, förhållandet mellan dess lista avkodning radie till dess minsta avstånd förblir oförändrad under tensor produktdrift (snarare än squaring, som man kan förvänta sig). Detta ger den första effektiva listan avkodare och nya kombinatoriska gränser för vissa naturliga koder inklusive multivariat polynomials där graden i varje variabel begränsas. (2) Vi visar att för varje kod, dess lista avkodning radie förblir oförändrad under m-wise interleating för ett heltal m. Detta generaliserar ett nyligen resultat av Dinur et al. [5], som bevisade ett sådant resultat för interleaded Hadamard koder (likvärdigt linjära omvandlingar). (3) Med hjälp av begreppet generaliserade Hamming vikter, ger vi bättre liststorlek gränser för både tensoring och interleaving av binära linjära koder. Genom att analysera viktfördelningen av dessa koder, minskar vi uppgiften att begränsa listans storlek till att begränsa antalet nära-by låg-rankade kodord. För avkodning av linjära omvandlingar, med rankreduktion tillsammans med andra idéer, får vi snäva liststorleksgränser för små fält. Våra resultat ger bättre gränser på listan avkodning radie än vad som erhålls från Johnson bundna, och ger ganska allmänna familjer av koder decodable bortom Johnson bundna. * Full version postad på http://arxiv.org/abs/0811.4395 † Arbete gjort delvis medan en postdoc vid University of Washington besöker Princeton University.
En annan metod kommer från listan-avkodning av tensor koder REF.
List decoding tensor products and interleaved codes
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}