46 citations · 63 across the 11 of their papers we have counts for
4 papers · 1 filter
Extractors for Images of Varieties
Zeyu Guo, Ben Lee Volk, Akhil Jalan +1
We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \m…
Deterministic Extractors for Additive Sources
Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê +1
We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmet…
Can Random Coin Flips Speed Up a Computer?
David Zuckerman
This expository essay introduces randomness and computation to a lay audience.
Pseudorandom Generators for Polynomial Threshold Functions
Raghu Meka, David Zuckerman
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/eps^{O(d)} f…