Za pracę On sets of integers containing no k elements in arithmetic progression opublikowaną w 1975 w Acta Arithmetica otrzymał w 2008 Nagrodę Steele'a za znaczący wkład w badania. Jej główny wynik, znany dziś jako twierdzenie Szemerédiego, potwierdził z 1936 roku. Aby go otrzymać sformułował i wykazał tzw. . który okazał się niezwykle istotny w teorii grafów i informatyce teoretycznej. Zdaniem laureata Medalu Fieldsa Timothy'ego Gowersa twierdzenie to jest jednym z najważniejszych osiągnięć matematyki w XX wieku, a lemat o regularności stał się jednym z głównych narzędzi .
Kolejnym ważnym wynikiem Szemerédiego jest podanie, w opublikowanej w 1980 roku pracy (współautorzy i Janós Komlós) A note on Ramsey numbers, ograniczenia górnego liczb Ramseya R(3, k).
W 1982 wraz z Komlósem i Jánosem Pintzem (artykuł A lower bound for Heilbronn’s problem) podał kontrprzykład na ponad trzydziestoletnią z geometrii kombinatorycznej.
W 1983 w pracy An 0(n log n) sorting network Szemerédi, Ajtai i Komlós przedstawili optymalną sieć sortującą, znaną obecnie jako sieć AKS.
Inne rezultaty nazwane jego nazwiskiem to np.