The Taub Faculty of Computer Science Events and Talks

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.