Stochastics/Discrete Analysis Seminar: Chin Ho Lee, NC State Computer Science, The trace reconstruction problem
SAS 4201The trace reconstruction problem asks to reconstruct an unknown n-bit string x given independent random "traces" of x, where a random trace is obtained by first deleting each bit of x independently with some probability (say 0.5), and then outputting the concatenation of the remaining bits of x. A basic question is to determine the…