  Given a set of $n$ real numbers, the 3SUM problem is to decide whether there
are three of them that sum to zero. Until a recent breakthrough by Gr{\o}nlund
and Pettie [FOCS'14], a simple $\Theta(n^2)$-time deterministic algorithm for
this problem was conjectured to be optimal. Over the years many algorithmic
problems have been shown to be reducible from the 3SUM problem or its variants,
including the more generalized forms of the problem, such as $k$-SUM and
$k$-variate linear degeneracy testing ($k$-LDT). The conjectured hardness of
these problems have become extremely popular for basing conditional lower
bounds for numerous algorithmic problems in P.
  In this paper, we show that the randomized $4$-linear decision tree
complexity of 3SUM is $O(n^{3/2})$, and that the randomized $(2k-2)$-linear
decision tree complexity of $k$-SUM and $k$-LDT is $O(n^{k/2})$, for any odd
$k\ge 3$. These bounds improve (albeit randomized) the corresponding
$O(n^{3/2}\sqrt{\log n})$ and $O(n^{k/2}\sqrt{\log n})$ decision tree bounds
obtained by Gr{\o}nlund and Pettie. Our technique includes a specialized
randomized variant of fractional cascading data structure. Additionally, we
give another deterministic algorithm for 3SUM that runs in $O(n^2 \log\log n /
\log n )$ time. The latter bound matches a recent independent bound by Freund
[Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use
of word-RAM model.
