Paper Info
Title
A Fixed-Depth Size-Hierarchy Theorem For Ac(0)[Circle Plus] Via The Coin Problem
Abstract
In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform AC(0)[circle plus]. In particular, we show that for any fixed d and integer parameter k, the class Cd, k of functions that have uniform AC(0)[circle plus] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform AC(0)[circle plus] formulas of size nk but no AC(0)[circle plus] formulas of size less than n(epsilon 0k) for some absolute constant epsilon(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 + d)/2 or (1 - d)/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 AC(0) formulas (i.e., made up of AND and OR gates only) solving the d-coin problem that have depth d, size exp(O(d center dot(1/delta)(1/(d-1)))), and sample complexity (i.e., number of inputs) 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 center dot (1/delta)(1/(d-1)))) to 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 AC(0)[circle plus] formulas (which are also allowed NOT and Parity gates): formally, we show that any AC(0)[circle plus] formula solving the d-coin problem must have size exp(O(d center dot (1/delta)1/(delta-1))). This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122-3154], who prove an exp(O((1/d)1/(d+2))) lower bound for AC(0)[circle plus] 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(O((1/delta)1/(delta-1))) lower bound for 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 F2 solving the d-coin problem, which may be of independent interest.
Year
DOI
Venue
2021
10.1137/19M1276467
SIAM JOURNAL ON COMPUTING
Keywords
DocType
Volume
constant-depth circuits, coin problem, explicit constructions, combinatorial designs, Janson's inequality, multivariate polynomials
Journal
50
Issue
ISSN
Citations 
4
0097-5397
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Nutan Limaye113420.59
Karteek Sreenivasaiah2135.30
Srikanth Srinivasan313221.31
Utkarsh Tripathi413.05
S. Venkitesh513.05