On the Threshold for Szemerédi's Theorem with Random Differences

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 N1-2/k + o(1) for length-k progressions. This improves the previous best bounds of N1-1/ k/2 + o(1) for all odd k.