This year's Abel Prize, one of the most prestigious awards in mathematics, has gone to Endre Szemerédi, a pure mathematician who has provided a number of results that have been important in computer science.
The Norwegian Academy of Science and Letters established the Abel Prize, which is worth 6 million Norwegian kroner (around $1 million US) in 2003.
It has been awarded to Endre Szemerédi,
"for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory".
According to Nils Stenseth, president of the academy, who announced the award, Szemerédi's work:
"..supplies some of the basis for the whole development of informatics and the Internet. He showed how number theory can be used to organize large amounts of information in efficient ways."
Szemerédi and his Hungarian collaborators Miklós Ajtai and Janós Komlós discovered an optimal sorting network for parallel processing in 1983, but he is best known for the theorem, proved in 1975, that establishes the presence of arbitrarily long arithmetic progressions within any set of integers that has nonzero limiting density. Roughly speaking, this means that if you take an infinite set of integers that has enough diversity then you can still find runs of arithmetic progressions of any length.
This had been an unsolved problem for decades after it was first posed in 1936 by Hungarian mathematicians Paul Turán and Paul Erdös.
As part of the proof he also provided a tool, known as the Szemerédi regularity lemma, which gives a deeper understanding of large graphs or networks. This lemma asserts that every graph can be partitioned into roughly equal parts so that the connections between the parts are essentially pseudo random.
The lemma has also helped with understanding the artificial intelligence idea known as "Probably Approximately Correct" or PAC learning".
Szemerédi holds positions both at the Alfréd Rényi Institute of Mathematics in Budapest and Rutgers University and has published over 200 papers, spanning five decades. At the age of 71, he continues active research work, and according to colleagues shows no signs of slowing down.
In their foreword to An Irregular Mind: Szemerédi is 70, a volume in the Bolyai Society Mathematical Studies published by Springer (see side panel), Imre Bárány and Jozsef Solymosi point out:
Szemeredi has an "irregular mind", his brain is wired differently than for most mathematicians. Many of us admire his unique way of thinking, his extraordinary vision. His coauthors often mention that Szemeredi sees things differently, that he is able to find the hidden structure, or able to create one, out of thin air. His insistence that such a structure would work has often proved decisive.
Although Szerneredi's research interest is combinatiorics, number theory and computer science, his influence on other fields of mathematics, ergodic theory and analysis for instance, is remarkable.
This volume, published to mark Szemerédi's 70th birthday, in 2010 is a collection of research papers contributed by his colleagues and friends. The topics include extension and applications of the regularity lemma, the existence of k-term arithmetic progressions, in various subsets of the integers, extremal problems in hypergraphs theory, and random graphs.
Every year Donald Knuth traditionally gives a lecture inspired by some tree-like topic, and even though he gave up the tree theme a year or two ago, the lecture is still called the Christmas Tree Lect [ ... ]