For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Complexity of Threshold Circuits for Parity Functions
Shao-Chin SUNG Tetsuro NISHINO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/01/25
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
computational complexity, threshold circuit, parity function,
Full Text: PDF(221.7KB)>>
In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2clog n)/c), for all 1c [log(n+1)]-1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks, we also show an Ω (log n/log log n) lower bound for the depth of the threshold circuits. This is an answer to the open question posed in .