  In the classical linear degeneracy testing problem, we are given $n$ real
numbers and a $k$-variate linear polynomial $F$, for some constant $k$, and
have to determine whether there exist $k$ numbers $a_1,\ldots,a_k$ from the set
such that $F(a_1,\ldots,a_k) = 0$. We consider a generalization of this problem
in which $F$ is an arbitrary constant-degree polynomial, we are given $k$ sets
of $n$ numbers, and have to determine whether there exist a $k$-tuple of
numbers, one in each set, on which $F$ vanishes. We give the first improvement
over the na\"ive $O^*(n^{k-1})$ algorithm for this problem (where the
$O^*(\cdot)$ notation omits subpolynomial factors).
  We show that the problem can be solved in time $O^*\left( n^{k - 2 + \frac
4{k+2}}\right)$ for even $k$ and in time $O^*\left( n^{k - 2 +
\frac{4k-8}{k^2-5}}\right)$ for odd $k$ in the real RAM model of computation.
We also prove that for $k=4$, the problem can be solved in time
$O^*(n^{2.625})$ in the algebraic decision tree model, and for $k=5$ it can be
solved in time $O^*(n^{3.56})$ in the same model, both improving on the above
uniform bounds.
  All our results rely on an algebraic generalization of the standard
meet-in-the-middle algorithm for $k$-SUM, powered by recent algorithmic
advances in the polynomial method for semi-algebraic range searching. In fact,
our main technical result is much more broadly applicable, as it provides a
general tool for detecting incidences and other interactions between points and
algebraic surfaces in any dimension. In particular, it yields an efficient
algorithm for a general, algebraic version of Hopcroft's point-line incidence
detection problem in any dimension.
