  Using recent developments on the theory of locally decodable codes, we prove
that the critical size for Szemer\'edi's theorem with random differences is
bounded from above by $N^{1-\frac{2}{k} + o(1)}$ for length-$k$ progressions.
This gives polynomial improvements over the previous best bounds for all odd
$k$.
