The complexity of the parity function in unbounded fan-in, unbounded depth circuits (Q1183575)

An involved study of the complexity of the parity function \(f_ n\) of \(n\) variables realised by unbounded fan-in Boolean circuits is presented. The number of gates of a circuit is considered as the main complexity measure, but the number of wires is also investigated in some cases. Several optimal and almost optimal (lower and upper) bounds on the complexity of \(f_ n\) for distinct bases are established. The proof techniques used include several nice ideas, and are interesting for everybody working in Boolean function complexity theory.