Limaye, Nutan and Sreenivasaiah, Karteek and Srinivasan, Srikanth et. al.
(2019)
A fixeddepth sizehierarchy theorem for AC0[⊕] via the coin problem.
In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 23  26 June 2019, Phoenix, AZ, USA.
Full text not available from this repository.
(
Request a copy)
Abstract
In this work we prove the first Fixeddepth SizeHierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, 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 explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC0[⊕] formulas.
The explicit functions are derived from the δCoin Problem, which is the computational problem of distinguishing between coins that are heads with probability (1+δ)/2 or (1−δ)/2, where δ 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.
Upper bounds. For any constant d≥ 2, we show that there are explicit monotone AC0 formulas (i.e. made up of AND and OR gates only) solving the δ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) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from exp(O(d(1/δ)1/(d−1))) to poly(1/δ).
Lower bounds. We show that the above 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(Ω(d(1/δ)1/(d−1))). This strengthens a result of Shaltiel and Viola (SICOMP 2010), who prove a exp(Ω((1/δ)1/(d+2))) lower bound for AC0[⊕], and a lower bound of exp(Ω((1/δ)1/(d−1))) shown by Cohen, Ganor and Raz (APPROXRANDOM 2014) for the class 0.
The upper bound is a derandomization involving a use of Janson’s inequality and classical combinatorial designs. The lower bound involves proving an optimal degree lower bound for polynomials over 2 solving the δcoin problem.
[error in script]
Actions (login required)

View Item 