In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC$^0[\oplus]$. In particular, we show that for any fixed $d$, the class $\mathcal{C}_{d,k}$ of functions that have uniform $\AC^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. We show this by exibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC$^0[\oplus]$ formulas.

The explicit functions are derived from the $\delta$-Coin Problem, which is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem and make progress on both upper bound and lower bound fronts.

Upper bounds. For any constant $d\geq 2$, we show that there are explicit monotone AC$^0$ formulas (i.e. made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e. number of inputs) $\poly(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from $\exp(O(d(1/\delta)^{1/(d-1)}))$ to $\poly(1/\delta)$.

Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of AC$^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any AC$^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d(1/\delta)^{1/(d-1)})).$ This strengthens a result of Shaltiel and Viola (SICOMP 2010), who prove a $\exp(\Omega((1/\delta)^{1/(d+2)}))$ lower bound for $\AC^0[\oplus]$, and a result of Cohen, Ganor and Raz (APPROX-RANDOM 2014), who show a $\exp(\Omega((1/\delta)^{1/(d-1)}))$ lower bound for the smaller class AC$^0$.

The upper bound is a derandomization involving a use of Janson's inequality (from probabilistic combinatorics) and classical combinatorial designs; as far as we know, this is the first such use of Janson's inequality. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over $\mathbb{F}_2$ solving the $\delta$-coin problem, which may be of independent interest.

In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC$^0[\oplus]$. In particular, we show that for any fixed $d$, the class $\mathcal{C}_{d,k}$ of functions that have uniform $\AC^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. We show this by exibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC$^0[\oplus]$ formulas.

The explicit functions are derived from the $\delta$-Coin Problem, which is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem and make progress on both upper bound and lower bound fronts.

Upper bounds. For any constant $d\geq 2$, we show that there are explicit monotone AC$^0$ formulas (i.e. made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e. number of inputs) $\poly(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from $\exp(O(d(1/\delta)^{1/(d-1)}))$ to $\poly(1/\delta)$.

Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of AC$^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any AC$^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d(1/\delta)^{1/(d-1)})).$ This strengthens a result of Shaltiel and Viola (SICOMP 2010), who prove a $\exp(\Omega((1/\delta)^{1/(d+2)}))$ lower bound for $\AC^0[\oplus]$, and a result of Cohen, Ganor and Raz (APPROX-RANDOM 2014), who show a $\exp(\Omega((1/\delta)^{1/(d-1)}))$ lower bound for the smaller class AC$^0$.

The upper bound is a derandomization involving a use of Janson's inequality (from probabilistic combinatorics) and classical combinatorial designs; as far as we know, this is the first such use of Janson's inequality. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over $\mathbb{F}_2$ solving the $\delta$-coin problem, which may be of independent interest.

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper bounds. For any constant $d\geq 2$, we show that there are explicit monotone $\mathrm{AC}^0$ formulas (i.e. made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e. number of inputs) $\mathrm{poly}(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from $\exp(O(d(1/\delta)^{1/(d-1)}))$ to $\mathrm{poly}(1/\delta)$.
2. Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of $\mathrm{AC}^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any $\mathrm{AC}^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d(1/\delta)^{1/(d-1)})).$ This strengthens a result of Cohen, Ganor and Raz (APPROX-RANDOM 2014), who prove a similar result for $\mathrm{AC}^0$, and a result of Shaltiel and Viola (SICOMP 2010), which implies a superpolynomially weaker (though still exponential) lower bound.

The above yields the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of $\mathrm{AC}^0[\oplus]$ formulas. In particular, this yields the first Fixed-depth Size-Hierarchy Theorem for the uniform version of this class: our results imply that for any fixed $d$, the class $\mathcal{C}_{d,k}$ of functions that have uniform $\mathrm{AC}^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy.

The proofs use many ideas. The upper bound is a derandomization involving a novel use of Janson's inequality (from probabilistic combinatorics) in this context and classical combinatorial designs. The lower bound is a modification of the Razborov-Smolensky polynomial method; in particular, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over $\mathbb{F}_2$ solving the $\delta$-coin problem, which may be independently interesting.