Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi'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$.