Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-157 | 10th September 2018 19:17

The Coin Problem in Constant Depth: Sample Complexity and Parity gates



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.

ISSN 1433-8092 | Imprint