
PreviousNext
We introduce a new method for proving explicit upper bounds
on the VC Dimension of general functional basis networks,
and prove as an application, for the first time, that the
VC Dimension of analog neural networks with the sigmoidal
activation function $\sigma(y)=1/1+e^{-y}$ ...
more >>>
We define the notion of a randomized branching program in
the natural way similar to the definition of a randomized
circuit. We exhibit an explicit function $f_{n}$ for which
we prove that:
1) $f_{n}$ can be computed by polynomial size randomized
...
more >>>
We establish significantly improved bounds on the performance of the greedy
algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our
improvements result from a new approach to both problems. In particular,
(a) we improve the known bound on the performance ratio of the greedy ...
more >>>
PreviousNext