Stasys Jukna
Computing threshold functions by depth-3 threshold
circuits with smaller thresholds of their gates
Abstract
We consider depth-3 unbounded fanin threshold circuits. Gates are
usual threshold functions $T^n_k$ which compute $1$ iff at least $k$
of the inputs are equal to $1$; the minimum $\min\{k, n-k+1\}$ is
the {\em threshold value} of this gate. We show that the function
$T^n_k$ cannot be computed by a small depth-3 threshold circuit with
threshold values of its gates much smaller than $k.$
[Journal version appeared in: Information Processing Letters,
56 (1995), 147-150]
Back to my home page