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

Limaye, Nutan and Sreenivasaiah, Karteek and Srinivasan, Srikanth and et al, . (2021) A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem. SIAM Journal on Computing, 50 (4). pp. 1461-1499. ISSN 0097-5397

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

Abstract

In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform AC0[⊕]. In particular, we show that for any fixed d and integer parameter k, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform AC0[⊕] formulas of size nk but no AC0[⊕] formulas of size less than ne0k for some absolute constant ϵ0 > 0. The uniform formulas are designed to solve the d-coin problem, which is the computational problem of distinguishing between coins that are heads with probability (1 + δ)/2 or (1 - δ)/2, where d 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 ≥ 2, we show that there are uniform monotone AC0 formulas (i.e., made up of AND and OR gates only) solving the d-coin problem that have depth d, size exp(O(d·(1/δ)1/(d-1))), and sample complexity (i.e., number of inputs) poly(1/δ). 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 · (1/δ)1/(d-1))) to poly(1/d). 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 AC0[⊕] formulas (which are also allowed NOT and Parity gates): formally, we show that any AC0[⊕] formula solving the δ-coin problem must have size exp(O(d · (1/d)1/(d-1))). This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122-3154], who prove an exp(Ω((1/δ)1/(d+2))) lower bound for AC0[⊕] 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(Ω((1/δ)1/(d-1))) lower bound for AC0 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 F2 solving the d-coin problem, which may be of independent interest. © 2021 Society for Industrial and Applied Mathematics.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Sreenivasaiah, Karteek	UNSPECIFIED

Item Type:

Article

Additional Information:

∗Received by the editors July 22, 2019; accepted for publication (in revised form) May 11, 2021; published electronically August 31, 2021. Preliminary versions of this paper appeared in the 2019 editions of the proceedings of the ACM Symposium on the Theory of Computing [LSS+19] and Foundations of Software Technology and Theoretical Computer Science [LST19]. https://doi.org/10.1137/19M1276467 Funding: The first and third authors were partially supported by grant MTR/2017/000909 from SERB, Government of India. The fourth author was supported by the Ph.D. scholarship of NBHM, DAE, Government of India. The fifth author was supported by the senior research fellowship of HRDG, CSIR, Government of India. †Indian Institute of Technology Bombay, Mumbai, India (nutan@cse.iitb.ac.in, srikanth@math. iitb.ac.in, utkarshtripathi.math@gmail.com, venkitesh.mail@gmail.com). ‡Indian Institute of Technology Hyderabad, Hyderabad, India (karteek@iith.ac.in).

Uncontrolled Keywords:

Coin problem; Combinatorial designs; Constant-depth circuits; Explicit constructions; Janson's inequality; Multivariate polynomials

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

03 Aug 2022 10:25

Last Modified:

03 Aug 2022 10:25