Unbounded Fan-in Circuits and Associative Functions: A Finite Semigroup Has Constant-Depth, Polynomial-Size Circuits Exactly When It Is GroupfreeResearch Paper
Constant-depth circuits with unbounded fan-in are the standard model of very fast parallel computation with cheap wide gates. The lower bound of Furst, Saxe and Sipser (1984, doi:10.1007/BF01744431) shows that parity is out of reach at polynomial size, and later work sharpened it, notably Håstad (1986, doi:10.1145/12130.12132). On the other side, binary…