Two source extractors for asymptotically optimal entropy, and (many) more

X Li - 2023 IEEE 64th Annual Symposium on Foundations of …, 2023 - ieeexplore.ieee.org
A long line of work in the past two decades or so established close connections between
several different pseudorandom objects and applications, including seeded or seedless non …

Extractors for images of varieties

Z Guo, BL Volk, A Jalan, D Zuckerman - Proceedings of the 55th Annual …, 2023 - dl.acm.org
We construct explicit deterministic extractors for polynomial images of varieties, that is,
distributions sampled by applying a low-degree polynomial map f: F qr→ F qn to an element …

Extractors for sum of two sources

E Chattopadhyay, JJ Liao - Proceedings of the 54th Annual ACM …, 2022 - dl.acm.org
We consider the problem of extracting randomness from sumset sources, a general class of
weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n, k, C)-sumset …

Recent Advances in Randomness Extraction

E Chattopadhyay - Entropy, 2022 - mdpi.com
The area of randomness extraction has seen interesting advances in recent years, with rapid
progress on many longstanding open problems, along with the introduction of many new …

Explicit directional affine extractors and improved hardness for linear branching programs

X Li, Y Zhong - arXiv preprint arXiv:2304.11495, 2023 - arxiv.org
In a recent work, Gryaznov, Pudl\'{a} k, and Talebanfard (CCC'22) introduced a stronger
version of affine extractors known as directional affine extractors, together with a …

Affine extractors and ac0-parity

X Huang, P Ivanov, E Viola - Approximation, Randomization, and …, 2022 - drops.dagstuhl.de
We study a simple and general template for constructing affine extractors by composing a
linear transformation with resilient functions. Using this we show that good affine extractors …

Almost Chor-Goldreich Sources and Adversarial Random Walks

D Doron, D Moshkovitz, J Oh… - Proceedings of the 55th …, 2023 - dl.acm.org
A Chor–Goldreich (CG) source is a sequence of random variables X= X 1∘…∘ X t, where
each X i∼{0, 1} d and X i has δ d min-entropy conditioned on any fixing of X 1∘…∘ X i− 1 …

Improved extractors for small-space sources

E Chattopadhyay, J Goodman - 2021 IEEE 62nd Annual …, 2022 - ieeexplore.ieee.org
We study the problem of extracting random bits from weak sources that are sampled by
algorithms with limited memory. This model of small-space sources was introduced by …

Hardness against linear branching programs and more

E Chattopadhyay, JJ Liao - Leibniz International Proceedings in …, 2023 - par.nsf.gov
In a recent work, Gryaznov, Pudlák and Talebanfard (CCC'22) introduced a linear variant of
read-once branching programs, with motivations from circuit and proof complexity. Such a …

Extractors for Polynomial Sources over 𝔽₂

E Chattopadhyay, J Goodman… - 15th Innovations in …, 2024 - drops.dagstuhl.de
We explicitly construct the first nontrivial extractors for degree d≥ 2 polynomial sources over
𝔽₂. Our extractor requires min-entropy k≥ n-(√{log n})/((log log n/d)^{d/2}). Previously, no …