Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks (1996)
By Marek, Marek Karpinski, Angus Macintyre
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...
Approximating Dense Cases of Covering Problems (1996)
By Marek, Marek Karpinski, Alexander Zelikovsky
We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element belongs to at least fflm sets. We show that the...