I den vackert enkla-till-state problemet med spår rekonstruktion, är målet att rekonstruera en okänd binär sträng x givet slumpmässiga "spår" av x där varje spår genereras genom att ta bort varje koordinat av x oberoende med sannolikhet p < 1. Problemet studeras väl både när den okända strängen är godtycklig och när den väljs jämnt på måfå. För båda inställningarna finns det fortfarande ett exponentiellt gap mellan övre och nedre urvalskomplexitetsgränser och vår förståelse av problemet är fortfarande förvånansvärt begränsad. I detta dokument betraktar vi naturliga parameteriseringar och generaliseringar av detta problem i ett försök att uppnå en djupare och mer omfattande förståelse. Kanske våra mest överraskande resultat är: 1. Vi bevisar att exp(O(n 1/4 ε log n)) spår räcker för att rekonstruera godtyckliga matriser. I matrisversionen av problemet, varje rad och kolumn i en okänd ε n × ε n matris raderas självständigt med sannolikhet p. Våra resultat kontrasterar med de mest kända resultaten för sekvens rekonstruktion där den mest kända övre gränsen är exp (O(n 1/3 ) ). 2. Utgångspunkten är följande: Ett optimalt resultat för slumpmässig matrisrekonstruktion: vi visar att spår är nödvändiga och tillräckliga. Detta är i motsats till problemet för slumpmässiga sekvenser där det finns en superlogaritmisk nedre gräns och den mest kända övre gränsen är exp(O(log 1/3 n)). 3. Vad är det som händer? Vi visar att exp(O(k 1/3 log 2/3 n)) spår räcker för att rekonstruera k-sparse strängar, vilket ger en förbättring jämfört med de mest kända sekvens rekonstruktion resultat när k = k = o(n/ log 2 n). 4. Vad är det som händer? Vi visar att poly(n) spår räcker om x är k-sparse och vi dessutom har en "separation" löfte, särskilt att indexen för 1's i x alla skiljer sig åt genom  och (k log n).
I REF tar författarna hänsyn till problemen med att rekonstruera matriser och glesa strängar från spår.
Trace Reconstruction: Generalized and Parameterized
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}