Yan Zhong

Exponential Sampling Lower Bounds for Polynomial Sources

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...