Abstract | ||
---|---|---|
$textit{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 tending to $0$. We study this problemu0027s complexity in the model of constant-depth Boolean circuits and prove the following results. $textbf{Upper bounds.}$ For any constant $dgeq 2$, we show that there are $textit{explicit}$ monotone AC$^0$ formulas (i.e. made up of AND and OR gates only) solving the $delta$-coin problem, having depth $d$, size $exp(O(d(1/delta)^{1/(d-1)}))$, and sample complexity (no. of inputs) poly$(1/delta).$ This matches previous upper bounds of Ou0027Donnell 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 poly$(1/delta)$. $textbf{Lower bounds.}$ We show that the above upper bounds are nearly tight even for the significantly stronger model of AC$^0[oplus]$ formulas (i.e. allowing NOT and Parity gates): formally, we show that any 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 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 $textit{explicit}$ functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC$^0[oplus]$ formulas. In particular, this yields the first $textit{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 AC$^0[oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. |
Year | Venue | DocType |
---|---|---|
2018 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
25 | 1 | 0.35 |
References | Authors | |
10 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nutan Limaye | 1 | 134 | 20.59 |
Karteek Sreenivasaiah | 2 | 13 | 5.30 |
Srikanth Srinivasan | 3 | 132 | 21.31 |
Utkarsh Tripathi | 4 | 1 | 3.05 |
S. Venkitesh | 5 | 1 | 3.05 |