Szemerédi, Endre

Endre Szemerédi, (born August 21, 1940, Budapest, Hungary), Hungarian American mathematician awarded the 2012 Abel Prize “for his fundamental contributions to discrete mathematics and theoretical computer science.”

Szemerédi originally studied to become a doctor, but he soon dropped out of medical school and took a job in a factory. He then entered Eötvös Loránd University in Budapest, where he studied under Paul Erdős. He received a master’s degree in mathematics in 1965. He then earned a doctorate in mathematics at Moscow State University in 1970. He became a fellow at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences in Budapest, and from 1986 he was a professor of computer science at Rutgers University in New Brunswick, New Jersey.

One of his most noted contributions to mathematics is a theorem about arithmetic progressions. The theorem, which became known as Szemerédi’s theorem, proved a 1936 conjecture by Erdős and Hungarian mathematician Paul Turán. In number theory, an arithmetic progression is a sequence of numbers that proceeds in steps of the same amount. For example, 2, 4, 6, 8 is a progression with four terms and with 2 as the step size. Szemerédi’s theorem relies on the concept of density of a set of natural numbers. For some subset of the natural numbers, the density is the ratio between the number of integers in the intersection between that subset and the set {1,2,…,N} and N as N goes to infinity. Erdős and Turán conjectured that for a positive density d and any number of integers k, there is a number N(d,k) such that a subset of {1,2,…,N} that contains dN numbers has a k-term progression in it if N is greater than N(d,k). British mathematician Klaus Roth had proved the conjecture for three-term progressions in 1953. Szemerédi proved the conjecture for four-term progressions in 1969 and for progressions of any length in 1975. (Erdős often gave cash prizes to mathematicians for solving unsolved problems and regarded the conjecture as quite difficult. Szemerédi received $1,000 from Erdős for his proof.)

As part of Szemerédi’s general proof of the Erdős-Turán conjecture, he originated a key result in graph theory which became known as Szemerédi’s regularity lemma; it states that any graph can be broken up into smaller graphs that appear random. Szemerédi proved the lemma in a restricted form at first and then generally in 1978. The lemma proved extremely useful in graph theory, since it shows that results that apply to random graphs can be applied to graphs in general.

Despite Szemerédi’s stated indifference to computers, his work found many applications in computer science, most notably his collaboration with computer scientist Miklós Ajtai and mathematician (and Rutgers colleague) János Komlós on sorting. In 1983 the trio devised the Ajtai-Komlós-Szemerédi (AKS) sorting network, which is an algorithm for sorting n objects in a particular order in log n time steps, the least amount of time theoretically possible.