In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/4d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at most $s$;
$f_N$ does not have $AC^0[\oplus]$ formulas of depth $d$ and size $s^{\varepsilon}$, where $\varepsilon$ is a fixed absolute constant.

This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for $d \ll \log \log N$ and $s \ll \exp(N^{1/2^{\Omega(d)}})$.

As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity $(1/\delta)^{O(d)}$ (down from $(1/\delta)^{2^{O(d)}}$ in the previous result).

In our second result, we show that randomness buys depth in the $AC^0[\oplus]$ setting. Formally, we show that for any fixed constant $d\geq 2$, there is a family of Boolean functions that has polynomial-sized randomized uniform $AC^0$ circuits of depth $d$ but no polynomial-sized (deterministic) $AC^0[\oplus]$ circuits of depth $d$.

Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least $2$) is essential to avoid superpolynomial blow-up while derandomizing randomized $AC^0$ circuits. We show that an increase in depth (by at least $1$) is essential even for $AC^0[\oplus]$.

As in Viola's result, the separating examples are promise variants of the Majority function on $N$ inputs that accept inputs of weight at least $N/2 + N/(\log N)^{d-1}$ and reject inputs of weight at most $N/2 - N/(\log N)^{d-1}$.

Many typos and minor errors corrected.

In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at most $s$;
$f_N$ does not have $AC^0[\oplus]$ formulas of depth $d$ and size $s^{\varepsilon}$, where $\varepsilon$ is a fixed absolute constant.

This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for $d \ll \log \log N$ and $s \ll \exp(N^{1/2^{\Omega(d)}})$.

As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity $(1/\delta)^{d+4}$ (down from $(1/\delta)^{2^{O(d)}}$ in the previous result).

In our second result, we show that randomness buys depth in the $AC^0[\oplus]$ setting. Formally, we show that for any fixed constant $d\geq 2$, there is a family of Boolean functions that has polynomial-sized randomized uniform $AC^0$ circuits of depth $d$ but no polynomial-sized (deterministic) $AC^0[\oplus]$ circuits of depth $d$.

Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least $2$) is essential to avoid superpolynomial blow-up while derandomizing randomized $AC^0$ circuits. We show that an increase in depth (by at least $1$) is essential even for $AC^0[\oplus]$.

As in Viola's result, the separating examples are promise variants of the Majority function on $N$ inputs that accept inputs of weight at least $N/2 + N/(\log N)^{d-1}$ and reject inputs of weight at most $N/2 - N/(\log N)^{d-1}$.