Explicit functions requiring larger than 4.5n size circuitsResearch Paper
A -circuit is a Boolean circuit in which every gate has fan-in two and may compute any of the sixteen binary Boolean functions. Whether has circuits of size for some constant is a long-standing open question; no superlinear lower bound for an explicit function is known. Even the constant in front of has moved slowly, and every…