Jake Maranzatto : Statistical Reconstruction Problems

Posted by Karoline Dubin , part of the Computer Science Theory Seminar.

At

Oct. 13, 2021, 3 p.m.

In

636 SEO

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.