Abstract: Noise is a general phenomenon that interferes with our ability to compute. Understanding computation in its presence is thus a fundamental topic in computer science. I will talk about how to exploit and cope with noise in the areas of unconditional derandomization and statistical reconstruction. The talk consists of two parts:

 

In the first part, I will present a new methodology that my collaborators and I developed to construct new pseudorandom generators and obtain new impossibility results. The idea is to start with standard primitives such as k-wise independence and perturb them with noise. Using this, we obtained new results for derandomizing space-bounded computation, Turing machines, and polynomials, with applications for error-correcting codes.

 

In the second part, I will survey a series of results my collaborators and I obtained for the trace reconstruction problem. In this problem, an unknown and unencoded source string is sent through a deletion channel which randomly deletes each bit and concatenates the surviving bits, yielding a trace. The goal is to reconstruct the source string given independent traces. We developed near-optimal algorithms for various settings that arise in practical scenarios: from worst-case to average-case; from low to high deletion rates, and from exact to approximate reconstruction.

Short Bio: Chin Ho Lee is a postdoctoral research fellow at Harvard University. Prior to that, he was a Croucher postdoctoral fellow at Columbia University. He received his Ph.D. from Northeastern University in 2019, where he was advised by Prof. Emanuele Viola. He is broadly interested in theoretical computer science, and is particularly interested in pseudorandomness, analysis of Boolean functions, and statistical reconstruction problems.