Optimal Shallow Circuits for Majority

Victor Lecomte, Prasanna Ramakrishnan

Four decades on, Håstad's classical $2^{\Omega (n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known ${\mathrm{AC}}^0$ circuit lower bound for any expl…