Size Bounds on Low Depth Circuits for Promise Majority

Abstract

We give two results on the size of AC0 circuits computing promise majority. ε-promise majority is majority promised that either at most an ε fraction of the input bits are 1 or at most ε are 0.  
- First, we show super-quadratic size lower bounds on both monotone and general depth-3 circuits for promise majority.  
- For any ε ∈ (0, 1/2), monotone depth-3 AC0 circuits for ε-promise majority have size Ω̃(ε³ n^{2 + (ln(1 - ε))/(ln(ε))}). 
- For any ε ∈ (0, 1/2), general depth-3 AC0 circuits for ε-promise majority have size Ω̃(ε³ n^{2 + (ln(1 - ε²))/(2ln(ε))}). These are the first quadratic size lower bounds for depth-3 ε-promise majority circuits for ε < 0.49.
- Second, we give both uniform and non-uniform sub-quadratic size constant-depth circuits for promise majority.  
- For integer k ≥ 1 and constant ε ∈ (0, 1/2), there exists monotone non uniform AC0 circuits of depth-(2 + 2 k) computing ε-promise majority with size Õ(n^{1/(1 - 2^{-k})}). 
- For integer k ≥ 1 and constant ε ∈ (0, 1/2), there exists monotone uniform AC0 circuit of depth-(2 + 2 k) computing ε-promise majority with size n^{1/(1 - (2/3) ^k) + o(1)}. These circuits are based on incremental improvements to existing depth-3 circuits for promise majority given by Ajtai [Miklós Ajtai, 1983] and Viola [Emanuele Viola, 2009] combined with a divide and conquer strategy.