Vikbara Reed-Solomon koder är en explicit familj av koder som uppnår optimal avvägning mellan hastighet och felkorrigering förmåga: specifikt, för alla ε > 0, författaren och Rudra (2006,08) presenterade en n O(1/ε) tid algoritm för att lista avkoda lämpliga vikta RS-koder för hastighet R från ett bråk 1 - R - ε av fel. Algoritmen är baserad på multivariat polynominterpolering och rotfinnande över förlängningsfält. Det noterades av Vadhan att interpolering av ett linjärt polynom räcker om man lägger sig till med en mindre avkodningsradie (men ändå tillräckligt för ett uttalande av ovanstående form). Här ger vi en enkel linjär-algebra baserad analys av denna variant som eliminerar behovet av beräknings dyrt rotfinnande steg över förlängningsfält (och faktiskt någon omnämnande av förlängningsfält). Hela listan avkodning algoritm är linjär-algebraic, lösa ett linjärt system för interpolation steg, och ett annat linjärt system för att hitta en liten subrymd av kandidatlösningar. Förutom steget att beskära subrymden, kan algoritmen implementeras för att köras i kvadratisk tid. Den teoretiska nackdelen med vikta RS-koder är att både avkodning komplexitet och bevisad värsta fall lista-storlek bundet är n  och (1/ε). Genom att kombinera ovanstående idé med en pseudorandom delmängd av alla polynom som meddelanden, får vi en Monte Carlo konstruktion som uppnår en lista storlek bundet av O(1/ε 2 ) som är ganska nära den existentiella O(1/ε) bundet (dock är avkodning komplexiteten n ∂(1/ε) ). Vårt arbete belyser att bygga en explicit subrymds-evasiv undergrupp som har liten skärningspunkt med lågdimensionella subrymder - ett intressant problem i pseudorandomness i sin egen rätt - kan leda till explicita koder med bättre listavkodningsgarantier.
Detta ger en uttrycklig version av koderna från REF, om än med en sämre lista storlek gränsande (1/ε) O(1/ε).
Linear-algebraic list decoding of folded Reed-Solomon codes
{'venue': '2011 IEEE 26th Annual Conference on Computational Complexity', 'journal': '2011 IEEE 26th Annual Conference on Computational Complexity', 'mag_field_of_study': ['Computer Science', 'Mathematics']}