Support Vector Machines are a family of algorithms for the 
analysis of data based on convex Quadratic Programming. 
We focus on their use for classification,
where the SVM algorithms work
by maximizing the margin of a classifying hyperplane in a feature space.
In this paper,
based on a variation of Random Sampling Techniques,
techniques successfully used for similar problems,
we derive a randomized algorithm for training SVMs
and formally prove an upper bound on the expected running time
which is quasilinear with respect to the number of data points.
To our knowledge,
this is the first algorithm with a quasilinear bound
that can handle SVMs with kernels.
% for which such a quasilinear bound has been formally proved.
(This is a full version of our conference paper.)