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 wires. Similarly, we obtain a lower bound for computing the depth 4 circuits.

Keywords: computational complexity, circuit complexity, boolean function complexity, lower bound, parity

Retrieve PDF document (200109_10.pdf)

Received January 7, 2000; revised May 11, 2000; accepted June 1, 2000.
Communicated by Hsu-Chun Yen.
^* The work was supported in part by the National Science Council of Taiwan under contact NSC 87-2213-E-260-001.