linear separability

[Chaim Gotsman]

The Baum paper from the last NIPS avoids the problem instances where the
classic perceptron algorithm runs in exponential time (where some of the
points of the hypercube are at an exponentially small distance from the
separating plane), by calling these points malicious and probabilistically
eliminating them.

I don't see why this makes the algorithm suddenly tractable "on the average".