Limaye, N and Sreenivasaiah, K. et al.
(2021)
A FixedDepth SizeHierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem.
SIAM J. Comput., 50 (4).
pp. 14611499.
ISSN 10957111
Full text not available from this repository.
(
Request a copy)
Abstract
In this paper, we prove the first fixeddepth sizehierarchy theorem for uniform ${\mathrm{AC}}^0[\oplus]$. In particular, we show that for any fixed $d$ and integer parameter $k$, 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. We show this by exhibiting the first class of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of size $n^k$ but no ${\mathrm{AC}}^0[\oplus]$ formulas of size less than $n^{\varepsilon_0 k}$ for some absolute constant $\varepsilon_0 > 0$. The uniform formulas are designed to solve the $\delta$coin problem, which 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 and make progress on both upper bound and lower bound fronts. Regarding Upper bounds, for any constant $d\geq 2$, we show that there are uniform 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\cdot(1/\delta)^{1/(d1)}))$, and sample complexity (i.e., number of inputs) ${\mathop{\mathrm{poly}}}(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer [ICALP 2007: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 195206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 5970] in terms of size (which is optimal), while improving the sample complexity from $\exp(O(d\cdot(1/\delta)^{1/(d1)}))$ to ${\mathop{\mathrm{poly}}}(1/\delta)$. The improved sample complexity is crucial for proving the sizehierarchy theorem. Regarding Lower bounds, we show that the preceding 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\cdot(1/\delta)^{1/(d1)})).$ This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 31223154], who prove an $\exp(\Omega((1/\delta)^{1/(d+2)}))$ lower bound for ${\mathrm{AC}}^0[\oplus]$ circuits, and a result of Cohen, Ganor, and Raz [APPROXRANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, LeibnizZentrum fuer Informatik, Wadern, 2014, pp. 618629], who show an $\exp(\Omega((1/\delta)^{1/(d1)}))$ lower bound for ${\mathrm{AC}}^0$ circuits. The upper bound is a derandomization involving a use of Janson's inequality and an extension of classical polynomialbased combinatorial designs. For the lower bound, 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 of independent interest.
[error in script]
Actions (login required)

View Item 