{"id":"arxiv/2609.06371","url":"https://arxiv.org/abs/2609.06371","tags":["cs.CC","math.CO"],"score":0,"title":"Exponential Sampling Lower Bounds for Polynomial Sources","domain":"cs.CC","source":"arxiv","authors":["Yan Zhong"],"reviews":0,"subject":"cs.CC","summary":"A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that $\\mathrm{Ber}(1/3)^{\\otimes 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\\geq1$, every degree-$d$ polynomial…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-06","reactions":{}}