On the threshold for Szemerédi's theorem with random differences

Jop Briët, Davi Castro-Silva

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-\…