Abstract
We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity. For any $\delta < \varepsilon$ and any constant $\alpha > 0$, our sampler uses $m + O(\log (1 / \delta))$ random bits to output $t = O((\frac{1}{\varepsilon^2} \log \frac{1}{\delta})^{1 + \alpha})$ samples $Z_1, \dots, Z_t \in \{0, 1\}^m$ such that for any function $f: \{0, 1\}^m \to [0, 1]$, [ \Pr\left[\left|\frac{1}{t}\sum_{i=1}^t f(Z_i) - \mathbb{E}[f]\right| \leq \varepsilon\right] \geq 1 - \delta. ] The randomness complexity is optimal up to a constant factor, and the sample complexity is optimal up to the $O((\frac{1}{\varepsilon^2} \log \frac{1}{\delta})^{\alpha})$ factor. Our technique generalizes to matrix samplers. A matrix sampler is defined similarly, except that $f: \{0, 1\}^m \to \mathbb{C}^{d \times d}$ and the absolute value is replaced by the spectral norm. Our matrix sampler achieves randomness complexity $m + \tilde O (\log(d / \delta))$ and sample complexity $ O((\frac{1}{\varepsilon^2} \log \frac{d}{\delta})^{1 + \alpha})$ for any constant $\alpha > 0$, both near-optimal with only a logarithmic factor in randomness complexity and an additional $\alpha$ exponent on the sample complexity. We use known connections with randomness extractors and list-decodable codes to give applications to these objects. Specifically, we give the first extractor construction with optimal seed length up to an arbitrarily small constant factor above 1, when the min-entropy $k = \beta n$ for a large enough constant $\beta < 1$.
Introduction
In the field of pseudorandomness, the efficiency of sampling is a fundamental concern. Zhiyang Xun and David Zuckerman from the University of Texas at Austin have introduced a major breakthrough: the first efficient "averaging samplers" that are simultaneously optimal in randomness complexity and nearly optimal in sample complexity. This work resolves a long-standing open problem and provides the first randomness extractor with an optimal seed length for high-entropy sources.
The Challenge of Efficient Sampling
Randomness is a finite and often expensive resource in computational algorithms. Many algorithms rely on sampling to estimate the average value of a function $f$ over a large domain. The Chernoff Bound provides a benchmark for accuracy: independent samples yield high accuracy with high probability. However, independent samples are costly because each requires new random bits.
An averaging sampler aims to match the accuracy of independent sampling while minimizing the number of random bits used. A known lower bound dictates that to achieve an error within $\epsilon$ with failure probability $\delta$, at least $m + \log(1/\delta)$ random bits are required. Previous constructions often sacrificed either bit optimality or sample optimality. This paper presents a construction that is nearly optimal in both dimensions.
Methodology: Sub-sampling and Almost $\ell$-wise Independence
The authors introduce a novel "sub-sampling" strategy combined with almost $\ell$-wise independence to achieve these results.
- Sampler Composition: The construction utilizes a two-layer approach. An existing "outer" sampler, which is bit-efficient but sample-heavy, is refined by an "inner" sampler that selects a subset of those samples.
- Almost $\ell$-wise Independence: The inner sampler generates "almost $\ell$-wise independent" samples. While truly independent samples are bit-intensive, almost $\ell$-wise independent samples—where any small subset appears nearly random—are significantly cheaper to produce. The authors demonstrate that this level of independence is sufficient to maintain the required estimation accuracy.
- Recursive Composition for Matrices: For matrix samplers, where functions map to matrices and accuracy is measured by the spectral norm, this composition is applied recursively. This technique effectively bypasses the "curse of dimensionality" that typically increases matrix sampling complexity by a factor of $d^2$.
Key Results and Applications
The proposed constructions significantly advance the state of the art for both scalar and matrix samplers.
As shown in Table 1, for any constant $\alpha > 0$, the new averaging sampler uses $m + O(\log(1/\delta))$ random bits and $O((1/\epsilon^2 \log(1/\delta))^{1+\alpha})$ samples. This represents the first construction to achieve optimal randomness complexity alongside near-optimal sample complexity.
In the domain of matrix samplers (Table 2), the authors achieve near-optimal randomness $m + \tilde{O}(\log(d/\delta))$ and sample complexity. By avoiding a simple union bound over matrix entries, they reduce the complexity dependence on the dimension $d$ to a logarithmic factor.
Beyond samplers, these results have immediate implications for other cryptographic and coding primitives:
- Randomness Extractors: The paper provides the first extractor construction with an optimal seed length (up to a tiny constant factor) for sources with high min-entropy ($k = \beta n$).
- List-Decodable Codes: The techniques yield new binary list-decodable codes with improved rates compared to previous best-known results.
Conclusion and Future Directions
While this work nearly resolves the primary open problem in averaging samplers, several avenues for future research remain. The sample complexity currently includes an extra exponent of $1+\alpha$; achieving perfect optimality ($\alpha = 0$) is a remaining challenge. Additionally, for matrix samplers, the randomness complexity could potentially be further reduced by eliminating the $\log \log d$ factor. Finally, while the new list-decodable codes offer excellent rates, reducing the current exponential list size to polynomial would enhance their practical utility.
Summary updated