On the Bias of Reed--Muller Codes over Odd Prime Fields
On the Bias of Reed--Muller Codes over Odd Prime Fields
We study the bias of random bounded-degree polynomials over odd prime fields and show that, with probability exponentially close to 1, $n$-variate polynomials of degree $d$ over $\mathbb{F}_p$ have bias at most $p^{-\Omega(n/d)}$. This also yields an exponential tail bound on the weight distribution of Reed--Muller codes over odd prime …