In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and uniform $\mathrm{AC}^0[\oplus]$ (and even $\mathrm{AC}^0$ ) circuits of polynomial size. This also implies a separation between randomized $\mathrm{AC}^0[\oplus]$ circuits of linear size and deterministic $\mathrm{AC}^0[\oplus]$ circuits of near-linear size.

Our proof using certifying polynomials extends the deterministic restrictions technique of Chaudhuri and Radhakrishnan, who showed that Approximate Majority cannot be computed by $\mathrm{AC}^0$ circuits of size $n^{1+o(1)}$. At the technical level, we show that for every $\mathrm{AC}^0[\oplus]$ circuit $C$ of near linear size, there is a low degree variety $V$ over $\mathbb{F}_2$ such that the restriction of $C$ to $V$ is constant.

We also prove other results exploring various aspects of the power of certifying polynomials. In the process, we show an essentially optimal lower bound of $\Omega(\log^{\Theta(d)}s \cdot \log (1/\epsilon))$ on the degree of $\epsilon$-approximating polynomials for $\mathrm{AC}^0[\oplus]$ circuits of size $s$.