Exponential Sampling Lower Bounds for Polynomial Sources
Abstract
A degree-d polynomial source is the output of a polynomial map of degree at most d over 𝔽2 on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that Ber(1/3)⊗ N has statistical distance 1−o(1) from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM '26) asked for an explicit target distribution at distance 1−exp(−NΩd(1)). We resolve both questions. For every fixed d≥1, every degree-d polynomial source has overlap at most exp(−cdN) with Ber(1/3)⊗ N, where cd>0 is independent of the seed length. For quadratics, c2=2−26 suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form a/2b for integers a and b≥0). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on d+1 inputs to uniform seed bits yields flat degree-(d+1) target distributions of entropy k with overlap exp(−Ωd(min{k,N−k})) against every degree-d source, for min{k,N−k}≥2(d+1). This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed d. The construction has locality d+1 and uses O(N) field operations to sample. At k=⌊ N/2⌋, it handles d≤(1−ε)log2N/3 with overlap exp(−Nε−o(1)) for fixed 0<ε<1. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.
Related
- Localization Lengths for Two-Dimensional Random Band Matrices: Stretched-Exponential Lower Bounds
- Exponential Lower Bounds for the Pfaffian Number of Graphs
- Finite-Data Error Bounds for Approximating the Koopman Operator: Sampling Measures, Super-Polynomial Convergence and Regularization
- Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus
- Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
BibTeX
@misc{zhong2026exponential,
title = {{Exponential Sampling Lower Bounds for Polynomial Sources}},
author = {Yan Zhong},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06371},
eprint = {2609.06371},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06371},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exponential Sampling Lower Bounds for Polynomial Sources
AU - Yan Zhong
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06371
UR - https://arxiv.org/abs/2609.06371
AB - A degree-d polynomial source is the output of a polynomial map of degree at most d over 𝔽_2 on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that Ber(1/3)^⊗ N has statistical distance 1−o(1) from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM '26) asked for an explicit target distribution at distance 1−exp(−N^Ω_d(1)). We resolve both questions. For every fixed d≥1, every degree-d polynomial source has overlap at most exp(−c_dN) with Ber(1/3)^⊗ N, where c_d>0 is independent of the seed length. For quadratics, c_2=2^−26 suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form a/2^b for integers a and b≥0). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on d+1 inputs to uniform seed bits yields flat degree-(d+1) target distributions of entropy k with overlap exp(−Ω_d(min{k,N−k})) against every degree-d source, for min{k,N−k}≥2(d+1). This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed d. The construction has locality d+1 and uses O(N) field operations to sample. At k=⌊ N/2⌋, it handles d≤(1−ε)log_2N/3 with overlap exp(−N^ε−o(1)) for fixed 0<ε<1. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.
ER -