Heged\H{u}s's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field $\mathbb{F}$ of characteristic $p > 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of Hamming weight $k\in [q,n-q]$ must also vanish at all points in $\{0,1\}^n$ of weight $k + q$. This lemma was used by Heged\H{u}s (2009) to give a solution to \emph{Galvin's problem}, an extremal problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-known multilinear circuit lower bounds; and by Hrube\v{s}, Ramamoorthy, Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-$2$ threshold circuits for computing some symmetric functions.

In this paper, we formulate a robust version of Heged\H{u}s's lemma. Informally, this version says that if a polynomial of degree $o(q)$ vanishes at most points of weight $k$, then it vanishes at many points of weight $k+q$. We prove this lemma and give the following three different applications.

1. Degree lower bounds for the coin problem: The \emph{$\delta$-Coin Problem} is the problem of distinguishing between a coin that is heads with probability $((1/2) + \delta)$ and a coin that is heads with probability $1/2$. We show that over a field of positive (fixed) characteristic, any polynomial that solves the $\delta$-coin problem with error $\varepsilon$ must have degree $\Omega(\frac{1}{\delta}\log(1/\varepsilon)),$ which is tight up to constant factors.

2. Probabilistic degree lower bounds: The \emph{Probabilistic degree} of a Boolean function is the minimum $d$ such that there is a random polynomial of degree $d$ that agrees with the function at each point with high probability. We give tight lower bounds on the probabilistic degree of \emph{every} symmetric Boolean function over positive (fixed) characteristic. As far as we know, this was not known even for some very simple functions such as unweighted Exact Threshold functions, and constant error.

3. A robust version of the combinatorial result of Heged\H{u}s (2009) mentioned above.