A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem

Limaye, N and Sreenivasaiah, K. et al. (2021) A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem. SIAM J. Comput., 50 (4). pp. 1461-1499. ISSN 1095-7111

Full text not available from this repository. (Request a copy)


In this paper, we prove the first fixed-depth size-hierarchy 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/(d-1)}))$, 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. 195--206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 59--70] in terms of size (which is optimal), while improving the sample complexity from $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$ to ${\mathop{\mathrm{poly}}}(1/\delta)$. The improved sample complexity is crucial for proving the size-hierarchy 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/(d-1)})).$ This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122--3154], 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 [APPROX-RANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Wadern, 2014, pp. 618--629], who show an $\exp(\Omega((1/\delta)^{1/(d-1)}))$ 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 polynomial-based 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]
IITH Creators:
IITH CreatorsORCiD
Sreenivasaiah, KarteekUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Combinatorial design, Computational problem, Constant factors, Derandomization, Integer parameters, Lecture Notes, Multivariate polynomial, Sample complexity
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 03 Nov 2021 06:50
Last Modified: 11 Mar 2022 07:27
URI: http://raiith.iith.ac.in/id/eprint/8871
Publisher URL: https://epubs.siam.org/doi/10.1137/19M1276467
OA policy: https://v2.sherpa.ac.uk/id/publication/13592
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8871 Statistics for this ePrint Item