Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.5, pp857-860 (September 2001)

A Depth 3 Circuit Lower Bound for the Parity Function

Shi-Chun Tsai
Information Management Department
National Chi-Nan University
Nantou, 545 Taiwan
E-mail: tsai@csie.ncnu.edu.tw

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

Full Text () 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.