The Coin Problem and AC^0[parity]
summary
Proves that the delta coin problem can be solved by explicit depth‑3 AC0[⊕] formulas using only poly(1/δ) samples (instead of exponentially many), yielding a quasi‑polynomial fixed‑depth size hierarchy for AC0[⊕]. Gives a matching hardness result: any depth‑3 AC0[⊕] circuit solving the coin problem requires size exp(Ω(1/√δ)). Argument combines Razborov‑Smolensky polynomial approximation methods with level‑1 Fourier coefficient bounds and a partial derandomization of O’Donnell–Wimmer style constructions.
AI-written summary · about