{
  "abstract": "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 source has overlap at most $\\exp(-c_dN)$ with $\\mathrm{Ber}(1/3)^{\\otimes 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\\geq0$). 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\\}\\geq2(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=\\lfloor N/2\\rfloor$, it handles $d\\leq(1-\\varepsilon)\\log_2N/3$ with overlap $\\exp(-N^{\\varepsilon-o(1)})$ for fixed $0<\\varepsilon<1$. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.06371",
  "author_total": 1,
  "authors": [
    {
      "name": "Yan Zhong"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/3w1jr2dp6d677.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.06371",
  "fulltext_url": null,
  "id": "3w1jr2dp6d677",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.06371",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Complexity and Algorithms in Graphs"
    ]
  ],
  "openalex": "W7212067240",
  "pdf_url": "https://arxiv.org/pdf/2609.06371",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-06",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/3w1jr2dp6d677.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:19:58Z",
      "native_id": "2609.06371",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.06371"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Exponential Sampling Lower Bounds for Polynomial Sources",
  "title_text": "Exponential Sampling Lower Bounds for Polynomial Sources",
  "type": "preprint",
  "updated_at": "2026-10-30T12:19:58Z",
  "url": "https://research.draconitic.com/paper/3w1jr2dp6d677",
  "venue": "arXiv",
  "versions": []
}