Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Bounded Independence Plus Noise and its Applications to Coding Theory and Pseudorandomness
event speaker icon
Chin Ho Lee (Northeastern University)
event date icon
Wednesday, 14.11.2018, 12:30
event location icon
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.