Optimal Explicit Small-Depth Formulas for the Coin Problem

The δ-Coin Problem is the problem of distinguishing between a sequence of coin tosses that come up Heads with probability either 1+δ/2 or 1−δ/2. The computational complexity of this problem in various models has been studied in many previous works with various applications related to derandomization, hierarchy theorems, cryptography and meta-complexity.