  We propose a new heuristic algorithm for solving random subset sum instances
$a_1, \ldots, a_n, t \in \mathbb{Z}_{2^n}$, which play a crucial role in
cryptographic constructions. Our algorithm is search tree-based and solves the
instances in a divide-and-conquer method using the representation method. From
a high level perspective, our algorithm is similar to the algorithm of
Howgrave-Graham-Joux (HGJ) and Becker-Coron-Joux (BCJ), but instead of
enumerating the initial lists we sample candidate solutions. So whereas HGJ and
BCJ are based on combinatorics, our analysis is stochastic. Our sampling
technique introduces variance that increases the amount of representations and
gives our algorithm more optimization flexibility. This results in the
remarkable and natural property that we improve with increasing search tree
depth.
  Whereas BCJ achieves the currently best known (heuristic) run time
$2^{0.291n}$ for random subset sum, we improve (heuristically) down to
$2^{0.255n}$ using a search tree of depth at least $13$.
  We also apply our subset algorithm to the decoding of random binary linear
codes, where we improve the best known run time of the Becker-Joux-May-Meurer
algorithm from $2^{0.048n}$ in the half distance decoding setting down to
$2^{0.042n}$.
