More on A C 0 [ ] and Variants of the Majority Function

摘要

In this paper we prove two results about A C 0 [ ] circuits. We show that for d ( N ) = o ( log N log log N ) and N s ( N ) 2 d N 1 4 d 2 there is an explicit family of functions f N : 0 1 N 0 1 such that f N has uniform A C 0 formulas of depth d and size at most s ; f N does not have A C 0 [ ] formulas of depth d and size s , where 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 Fixed-Depth Size-Hierarchy theorem but for d log log N and s exp ( N 1 2 ( 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 size-optimal formulas for solving the coin problem with improved sample complexity (1 ) O ( d ) (down from (1 ) 2 O ( d ) in the previous result).In our second result, we show that randomness buys depth in the A C 0 [ ] setting. Formally, we show that for any fixed constant d 2 , there is a family of Boolean functions that has polynomial-sized randomized uniform A C 0 circuits of depth d but no polynomial-sized (deterministic) A C 0 [ ] circuits of depth d .Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least 2 ) is essential to avoid superpolynomial blow-up while derandomizing randomized A C 0 circuits. We show that an increase in depth (by at least 1 ) is essential even for A C 0 [ ] . 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 ) d ? 1 and reject inputs of weight at most N 2 ? N ( log N ) d ? 1 .