Circular Trace Reconstruction

on YouTube ↗30m

" summary

Problem: reconstruct a circular binary string from independent deletion-channel traces (deletions prob q). Main claims: worst-case reconstruction uses exp(O(n^{1/3})) traces (up to logs) when N is N with at most two primes; average-case reconstruction uses polynomially many traces with K = k-deck with K=O(log n) and exponent depending on q; lower bound Ω(N^3) (up to logs). Tools: polynomial Q(Z) built from Nth roots of unity, an unbiased estimator H, cyclotomic-field arguments, Chernoff/Hellinger bounds, and inefficient pairwise tests; limitation: dependence on N’s prime factorization.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 0:10Linear Trace Reconstruction • Trace reconstruction: An unknown binary string of length is passed through a deletion channel which deletes each bit independently with a food probability, resulting in a trace. How can we reconstruct the original string from many independent traces? What is the sample complexity, ie, how many traces do we need to recover the string with high probability?
3. 6:34Worst-case Reconstruction • Let x be an unknown, arbitrary circular string of length that goes through the deletion channel with fixed deletion probability. Then
4. 21:39Average-case Reconstruction: Bounding the Probabilities . Given two circular strings and y of length and a strings of length in x and y, we want to bound the probabilities that and start with s away from each other