Theory Seminar: Bounded Independence Plus Noise and its Applications to Coding Theory and Pseudorandomness

Chin Ho Lee (Northeastern University)
Wednesday, 14.11.2018, 12:30
Taub 201

We show that bounded independent distributions under perturbation of noise fool product tests, which are products of bounded functions defined on disjoint inputs. These results have found applications in coding theory and pseudorandomness. In this talk, I will talk about communication and space lower bounds for decoding linear codes, and how to construct pseudorandom generators for product tests and space-bounded computation.

Based on joint works with Elad Haramaty and Emanuele Viola.

Back to the index of events