46 citations · 63 across the 11 of their papers we have counts for
13 papers
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…
Spectral Sparsification via Bounded-Independence Sampling
Dean Doron, Jack Murtagh, Salil Vadhan +1
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph on vertices described…
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami +2
The seminal result of Kahn, Kalai and Linial shows that a coalition of players can bias the outcome of any Boolean function with respe…
Bitcoin Beacon
Iddo Bentov, Ariel Gabizon, David Zuckerman
We examine a protocol that outputs unpredictable and publicly verifiable randomness, meaning that the output is unknown at the time that sta…
On Low Discrepancy Samplings in Product Spaces of Motion Groups
Chandrajit Bajaj, Abhishek Bhowmick, Eshan Chattopadhyay +1
Deterministically generating near-uniform point samplings of the motion groups like SO(3), SE(3) and their n-wise products SO(3)^n, SE(3)^n is fundamental to numerous applications…
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…