Limaye, Nutan and Sreenivasaiah, Karteek and Srinivasan, Srikanth and et al, .
(2021)
A FixedDepth SizeHierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem.
SIAM Journal on Computing, 50 (4).
pp. 14611499.
ISSN 00975397
Full text not available from this repository.
(
Request a copy)
Abstract
In this paper, we prove the first fixeddepth sizehierarchy 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 dcoin 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 dcoin problem that have depth d, size exp(O(d·(1/δ)1/(d1))), 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. 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 · (1/δ)1/(d1))) to poly(1/d). 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 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/(d1))). This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 31223154], who prove an exp(Ω((1/δ)1/(d+2))) lower bound for AC0[⊕] 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(Ω((1/δ)1/(d1))) 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 dcoin 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; Constantdepth 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 
URI: 
http://raiith.iith.ac.in/id/eprint/10074 
Publisher URL: 
http://doi.org/10.1137/19M1276467 
OA policy: 
https://v2.sherpa.ac.uk/id/publication/13592 
Related URLs: 

Actions (login required)

View Item 