The Complexity of Threshold Circuits for Parity Functions

Shao-Chin SUNG; Tetsuro NISHINO

The Complexity of Threshold Circuits for Parity Functions

Shao-Chin SUNG, Tetsuro NISHINO

Full Text Views

0

Cite this

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((2^clog 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].

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.1 pp.91-93

Publication Date: 1997/01/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Algorithm and Computational Complexity

Cite this

Copy

Shao-Chin SUNG, Tetsuro NISHINO, "The Complexity of Threshold Circuits for Parity Functions" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 1, pp. 91-93, January 1997, doi: .
Abstract: 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((2^clog 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].
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_1_91/_p

Copy

@ARTICLE{e80-d_1_91,
author={Shao-Chin SUNG, Tetsuro NISHINO, },
journal={IEICE TRANSACTIONS on Information},
title={The Complexity of Threshold Circuits for Parity Functions},
year={1997},
volume={E80-D},
number={1},
pages={91-93},
abstract={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((2^clog 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].},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - The Complexity of Threshold Circuits for Parity Functions
T2 - IEICE TRANSACTIONS on Information
SP - 91
EP - 93
AU - Shao-Chin SUNG
AU - Tetsuro NISHINO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1997
AB - 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((2^clog 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].
ER -