The Coin Problem in Constant Depth: Sample Complexity and Parity Gates
share
The δ-Coin Problem is the computational problem of distinguishing between coins that are heads with probability (1+δ)/2 or (1-δ)/2, where δ is a parameter tending to 0. We study this problem's complexity in the model of constant-depth Boolean circuits and prove the following results. Upper bounds. For any constant d≥ 2, we show that there are explicit monotone AC^0 formulas (i.e. made up of AND and OR gates only) solving the δ-coin problem, having depth d, size (O(d(1/δ)^1/(d-1))), and sample complexity (no. of inputs) poly(1/δ). 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 (O(d(1/δ)^1/(d-1))) to poly(1/δ). Lower bounds. We show that the above upper bounds are nearly tight even for the significantly stronger model of AC^0[⊕] formulas (i.e. allowing NOT and Parity gates): formally, we show that any AC^0[⊕] formula solving the δ-coin problem must have size (Ω(d(1/δ)^1/(d-1))). This strengthens a result of Cohen, Ganor and Raz (APPROX-RANDOM 2014), who prove a similar result for AC^0, and a result of Shaltiel and Viola (SICOMP 2010), which implies a superpolynomially weaker (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 AC^0[⊕] 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 C_d,k of functions that have uniform AC^0[⊕] formulas of depth d and size n^k form an infinite hierarchy.
READ FULL TEXT