All reports by Author David Zuckerman:

__
TR24-097
| 31st May 2024
__

Zhiyang Xun, David Zuckerman#### Near-Optimal Averaging Samplers

Revisions: 2

__
TR22-169
| 26th November 2022
__

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman#### Extractors for Images of Varieties

Revisions: 1

Zhiyang Xun, David Zuckerman

We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity for natural parameter choices. Specifically, for any constant $\alpha > 0$, for $\delta > 2^{-\mathrm{poly}(1 / \varepsilon)}$, it uses $m + O(\log (1 / \delta))$ random bits to output $t = O(\log(1 ... more >>>

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

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 \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>