{"id":"arxiv/2605.00995","url":"https://arxiv.org/abs/2605.00995","tags":["cs.CC","math.CO"],"score":0,"title":"On Sampling Lower Bounds for Polynomials","domain":"cs.CC","source":"arxiv","authors":["Mohammad Mahdi Khodabandeh","Igor Shinkar"],"reviews":0,"subject":"cs.CC","summary":"In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $P = (P_1,\\dots, P_n)$ of functions $P_i \\colon \\mathbb{F}_2^m \\to \\mathbb{F}_2$ defines a distribution over $\\{0,1\\}^n$ in the natural way: draw $X$ uniformly at random from $\\mathbb{F}_2^m$ and output $(P_1(X),\\dots, P_n(X)) \\in \\{0,1\\}^n$. We show that when $P$ is defined by polynomials of degree $d$, the total variation distance of $P$ from the product distribution $\\mathrm{Ber}(1/3)^{\\otimes n}$ is…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-01","reactions":{}}