Separating AC 0 from depth-2 majority circuits

We prove that AC 0 cannot be efficiently simulated by MAJºMAJ circuits. Namely, we construct an AC 0 circuit of depth 3 that requires MAJºMAJ circuits of size 2 Ω(n 1/5 ) . This matches Allender's classic result that AC 0 can be simulated by MAJºMAJºMAJ circuits of quasipolynomial size. Our proof is based on communication complexity. To obtain the above result, we develop a novel technique for communication lower bounds, the Degree/Discrepancy Theorem. This technique is a separate contribution of our paper. It translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function. Upper bounds on the discrepancy, in turn, immediately imply communication lower bounds as well as lower bounds against threshold circuits. As part of our proof, we use the Degree/Discrepancy Theorem to obtain an explicit AC 0 circuit of depth 3 that has discrepancy 2 -Ω(n 1/5 ) , under an explicit distribution. This yields the first known AC 0 function with exponentially small discrepancy. Finally, we apply our work to learning theory, showing that polynomial-size DNF and CNF formulas have margin complexity 2 Ω(n 1/5 ) .

Authors

• Alexander A. Sherstov

Keywords

• AC 0
• communication complexity
• discrepancy
• threshold circuits