Delete-inmatningskanalen tar som indata en bit sträng x  till {0, 1} n, och utdata en sträng där bitar har tagits bort och infogats självständigt på måfå. Problemet med spårrekonstruktion är att återställa x från många oberoende utgångar (kallade "spår") av den radering-inmatningskanal som tillämpas på x. Vi visar att om x väljs jämnt slumpmässigt, då exp(O(log 1/3 n)) spår räcker för att rekonstruera x med hög sannolikhet. De tidigare övre gränserna var exp(O(log 1/2 n)) för borttagningskanalen med borttagande sannolikhet mindre än 1/2, och exp(O(n 1/3 )) för det allmänna fallet. En viktig ingrediens i vårt bevis är en tvåstegs justering förfarande där vi uppskattar platsen i varje spår som motsvarar en given bit av x. Anpassningen görs genom att visa strängarna som slumpmässiga promenader, och jämföra de ökningar i promenaden som är förknippade med inmatningssträngen respektive spåret, respektive.
Den state-of-the-art resultat, bevisas av Holden, Pemantle, och Peres REF, säger att exp(log 1/3 n) spår räcker för att rekonstruera en slumpmässig n-bit sträng under godtycklig konstant borttagning sannolikhet.
Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}