Abstract
In this paper we prove two results about AC^0[oplus] circuits.
(1) We show that for d(N) = o(sqrt(log N/log log N)) and N <= s(N) <= 2^(dN^(1/4d^2)) there is an explicit family of functions {f_N:{0,1}^N  > {0,1}} such that
 f_N has uniform AC^0 formulas of depth d and size at most s;
 f_N does not have AC^0[oplus] formulas of depth d and size s^epsilon, where epsilon is a fixed absolute constant.
This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar FixedDepth SizeHierarchy theorem but for d << log log N and s << exp(N^(1/2^Omega(d))).
As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform sizeoptimal formulas for solving the coin problem with improved sample complexity (1/delta)^O(d) (down from (1/delta)^(2^O(d)) in the previous result).
(2) In our second result, we show that randomness buys depth in the AC^0[oplus] setting. Formally, we show that for any fixed constant d >= 2, there is a family of Boolean functions that has polynomialsized randomized uniform AC^0 circuits of depth d but no polynomialsized (deterministic) AC^0[oplus] circuits of depth d.
Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least 2) is essential to avoid superpolynomial blowup while derandomizing randomized AC^0 circuits. We show that an increase in depth (by at least 1) is essential even for AC^0[oplus].
As in Viola's result, the separating examples are promise variants of the Majority function on N inputs that accept inputs of weight at least N/2 + N/(log N)^(d1) and reject inputs of weight at most N/2  N/(log N)^(d1).
BibTeX  Entry
@InProceedings{limaye_et_al:LIPIcs:2019:11584,
author = {Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi},
title = {{More on AC^0[oplus] and Variants of the Majority Function}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {22:122:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771313},
ISSN = {18688969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11584},
URN = {urn:nbn:de:0030drops115844},
doi = {10.4230/LIPIcs.FSTTCS.2019.22},
annote = {Keywords: AC^0[oplus], Coin Problem, Promise Majority}
}
Keywords: 

AC^0[oplus], Coin Problem, Promise Majority 
Collection: 

39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) 
Issue Date: 

2019 
Date of publication: 

04.12.2019 