Vi visar att listan-decodability av slumpmässiga linjära koder är lika bra som den allmänna slumpmässiga koder. För varje fast ändligt fält Fq, p 0, 1 − 1/q) och ε > 0, visar vi att med hög sannolikhet en slumpmässig linjär kod C i F n q av hastigheten (1 − Hq(p) − ε) kan lista avkodas från en bråkdel p av fel med listor över storlek som mest O(1/ε). Detta besvarar också en grundläggande öppen fråga om förekomsten av höglistade linjära koder, som visar att en listas storlek av O(1/ε) räcker för att ha en hastighet inom ε av den "lista avkodningskapaciteten" 1 − Hq(p). Den mest kända liststorleken var q O(1/ε) (utom i q = 2 fall där en lista-storlek gräns för O(1/ε) var känd). Den viktigaste tekniska ingrediensen i vårt bevis är en stark övre gräns för sannolikheten för att slumpmässiga vektorer som väljs från en hamming boll centrerad vid ursprunget har för många (mer än  på) vektorer från deras linjära spännvidd också tillhör bollen.
När ρ är konstant visar Guruswami, Håstad och Koppart Ref att en slumpmässig linjär kod för hastighet 1−Hq
On the list-decodability of random linear codes
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}