On the VC-Dimension of Depth Four Threshold Circuits and the Complexity of Boolean-Valued Functions

Abstract

We consider the problem of determining VC-dimension ∂_3( h ) of depth four n -input 1-output threshold circuits with h elements. Best known asymptotic lower bounds and upper bounds are proved, that is, when h → ∞ , ∂_3( h ) is upper bounded by (( h ^2/3)+ nh (log h )(1+ o (1))) and lower bounded by (1/2)(( h ^2/4)+ nh )(log h )(1 − o (1)). We also consider the problem of determining complexity c _3( N ) of Boolean-valued functions defined on N -pointsets in R ^n, measured by the number of threshold elements, with which we can construct a depth four circuit to realize the functions. We also show the best known upper and lower bounds, that is, when N → ∞, the complexity is upper bounded by $\sqrt {16\left( {{N \mathord{\left/{\vphantom {N {\log N}}} \right.\kern-\nulldelimiterspace} {\log N}}} \right)\left( {1 + o(1)} \right) + 4n^2 } - 2n$ and lower bounded by $\sqrt {6\left( {{N \mathord{\left/{\vphantom {N {\log N}}} \right.\kern-\nulldelimiterspace} {\log N}}} \right)\left( {1 + o(1)} \right)\left( {{9 \mathord{\left/{\vphantom {9 4}} \right.\kern-\nulldelimiterspace} 4}} \right)n^2 } - \left( {{3 \mathord{\left/{\vphantom {3 2}} \right.\kern-\nulldelimiterspace} 2}} \right)n$