In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform AC0[⊕]. In particular, we show that for any fixed d and integer parameter k, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform AC0[⊕] formulas of size nk but no AC0[⊕] formulas of size less than ne0k for some absolute constant ϵ0 > 0. The uniform formulas are designed to solve the d-coin problem, which is the computational problem of distinguishing between coins that are heads with probability (1 + δ)/2 or (1 - δ)/2, where d 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. Regarding Upper bounds, for any constant d ≥ 2, we show that there are uniform monotone AC0 formulas (i.e., made up of AND and OR gates only) solving the d-coin problem that have depth d, size exp(O(d·(1/δ)1/(d-1))), and sample complexity (i.e., number of inputs) poly(1/δ). This matches previous upper bounds of O'Donnell and Wimmer [ICALP 2007: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 195-206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 59-70] in terms of size (which is optimal), while improving the sample complexity from exp(O(d · (1/δ)1/(d-1))) to poly(1/d). The improved sample complexity is crucial for proving the size-hierarchy theorem. Regarding Lower bounds, we show that the preceding upper bounds are nearly tight (in terms of size) even for the significantly stronger model of AC0[⊕] formulas (which are also allowed NOT and Parity gates): formally, we show that any AC0[⊕] formula solving the δ-coin problem must have size exp(O(d · (1/d)1/(d-1))). This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122-3154], who prove an exp(Ω((1/δ)1/(d+2))) lower bound for AC0[⊕] circuits, and a result of Cohen, Ganor, and Raz [APPROX-RANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Wadern, 2014, pp. 618-629], who show an exp(Ω((1/δ)1/(d-1))) lower bound for AC0 circuits. The upper bound is a derandomization involving a use of Janson's inequality and an extension of classical polynomialbased combinatorial designs. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over F2 solving the d-coin problem, which may be of independent interest. © 2021 Society for Industrial and Applied Mathematics.