The Complexity of Threshold Circuits for Parity Functions

Shao-Chin SUNG  Tetsuro NISHINO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.1   pp.91-93
Publication Date: 1997/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexity,  threshold circuit,  parity function,  

Full Text: PDF(221.7KB)>>
Buy this Article




Summary: 
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[5], 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 [11].