On Sampling Lower Bounds for Polynomials

Mohammad Mahdi Khodabandeh, Igor Shinkar · 2026

Read On Sampling Lower Bounds for Polynomials by Mohammad Mahdi Khodabandeh, Igor Shinkar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00995.txt.

Description

Mohammad Mahdi Khodabandeh and Igor Shinkar prove lower bounds for samplers defined by low-degree polynomials over binary fields. Such a sampler draws a random input and outputs values of several polynomials, defining a distribution on binary strings. The authors show that when the polynomials have constant degree, the resulting distribution stays at total variation distance close to maximal from a specific product distribution with bias one third.

Concrete exponential bounds are given for degrees one, two, and three. A key step, of independent interest, shows any low-degree polynomial's output probability is bounded away from one third by a constant depending only on degree. The proof uses structural results that a biased low-degree polynomial can be written using few lower-degree polynomials.

Catalog record

CREATORMohammad Mahdi Khodabandeh, Igor Shinkar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE148 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00995

Browse the full library · About the Tower of Babel