Fitting a parabola to separate two classes of points in the plane

A Support Vector Machine might be able to do it. Suppose we map your 2D $(x,y)$ space to 3D $(x,x^2,y)$. An SVM will find a plane in this space, of the form $a x + b x^2 + c y = d$ which optimally separates the classes. Solving for y we get $y = \frac{d}{c} - \frac{a}{c} x - \frac{b}{c} x^2$ which is indeed the equation of a parabola. SVMs can be made robust against the possibility that a separating plane (parabola) does not exist, they will still find the "best" solution in some sense, and afterwards you can check (in linear time) whether the solution actually separates the classes (also see this question).

I am not certain whether you can train such an SVM in linear time. This paper suggests that it can be done.