Suppose we have a set of points $(x,y)$ in the plane where each point is either boy or a girl. Does there exists a randomized linear-time algorithm to determine if we can fit a parabola (given by a polynomial $ax^2+bx+c$) that separates the boys from girls in the plane?
In addition to finding such a parabola if one exists, how can the algorithm detect if no such parabola exists and terminate?
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.