Vi studerar koder som är lista-decodable under tillägg och raderingar ("insdel koder"). Specifikt, vi anser att inställningen där, med tanke på ett kodord x längd n över vissa ändliga alfabetet  på storlek q, δ · n kodord symboler kan vara motsträvigt bort och γ · n symboler kan motsträvigt infogas för att ge ett korrumperat ord w. En kod sägs vara lista-decodable om det finns en (effektiv) algoritm som, givet w, rapporterar en liten lista med kodord som inkluderar det ursprungliga kodordet x. Med tanke på δ och γ studerar vi vad som är den hastighet R för vilken det finns en konstant q och lista storlek L sådan att det finns koder för hastighet R korrigera δ-fraktion tillägg och γ-fraktion borttagningar medan rapportering listor av storlek som mest L. Använda begreppet synkronisering strängar, infördes av de två första författarna [Proc. STOC 2017], visar vi några överraskande resultat. Vi visar att för varje 0 ≤ δ < 1, varje 0 ≤ γ < γ och varje ε > 0 finns koder för hastighet 1 − ε och konstant alfabet (so q = O ε,γ,ε (1)) och underlogaritmiska liststorlekar. Dessutom åtföljs våra koder av effektiva (polynomisk tid) avkodningsalgoritmer. Vi betonar att andelen inlägg kan vara godtyckligt stor (mer än 100%), och hastigheten är oberoende av denna parameter. Vi visar också flera snäva gränser på parametrarna för list-decodable insdel koder. I synnerhet visar vi att alfabetets storlek på insdelkoder måste vara exponentiellt stor i ε −1, där ε är gapet till kapaciteten ovan. Vårt resultat gäller även inställningar där den unika avkodningskapaciteten motsvarar listavkodningskapaciteten och när den gör det visar det att alfabetets storlek måste vara exponentiellt stor i gapet till kapacitet. Detta är skarp kontrast till Hamming-felmodellen där alfabetets storlek polynom i ε −1 räcker för unik avkodning. Denna lägre gräns visar också att det exponentiella beroendet av alfabetets storlek i tidigare verk som konstruerat insdelkoder faktiskt är nödvändigt! Vårt resultat kastar ljus över den anmärkningsvärda asymmetrin mellan effekterna av införanden och raderingar med avseende på felkorrigering: Medan raderingskostnader i takt med koden, implementationskostnader bärs av motståndaren och inte koden! Våra resultat belyser också dominansen av modellen för införanden och raderingar över Hamming-modellen: Ett Hamming-fel är lika med ett införande och en radering (på samma plats). Således effekten av δ-fraktion Hamming fel kan simuleras genom δ-fraktion av raderingar och δ-fraktion av insättningar - men insdel koder kan hantera mycket fler insättningar utan förlust i takt (även om till priset av högre alfabet storlek).
Resultatet i REF gäller dock endast för tillräckligt stora konstanta alfabetsstorlekar, och det belyser inte listan-decodability av binära (eller något fast alfabet) insdelkoder.
Synchronization Strings: List Decoding for Insertions and Deletions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}