Computer Science Theory Seminar
Jake Maranzatto
UIC
Statistical Reconstruction Problems
Abstract: The goal of statistical reconstruction problems is to quantify how many noisy samples are required to recover a target object with high probability. The canonical example is string trace reconstruction, where bits in a binary string are removed i.i.d to produce samples, and our goal is to design an algorithm to recover the original string with high probability. I'll discuss the history of string reconstruction, as well as some of my work on reconstructing trees.
Wednesday October 13, 2021 at 3:00 PM in 636 SEO