Small-bias sample spaces are probability distributions that can fool parity functions, making them useful for derandomization, error-correcting codes, and probabilistically checkable proofs. They require fewer random bits than the uniform distribution to fool parities, and are equivalent to ϵ \epsilon -balanced error-correcting codes.
UC Berkeley
Fall 2021
This course explores the role of randomness in computation and pseudorandomness, focusing on the applications in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. The course will also address the question of derandomization of small-space computation. Prerequisites are unspecified, but the course content suggests a high level of expertise.
No concepts data
+ 26 more concepts