A depth 3 circuit lower bound for the parity function
Shi‐Chun Tsai · Journal of information science and engineering · 2001
We consider small depth boolean circuits with basis {AND, OR, NOT}. We obtain lower bounds for the parity function using a relatively simple method. We prove that for any depth 3 circuit with top fan-in t, computing the n-variable parity function must have at least t n t 1 2 − wires. Similarly, we obtain a lower bound for computing the depth 4 circuits.