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
| CREATOR | Mohammad Mahdi Khodabandeh, Igor Shinkar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 148 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00995