Szemerédi Awarded Abel Prize
Szemerédi Awarded Abel Prize
Written by Sue Gee   
Friday, 23 March 2012

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: 

" 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.



blog comments powered by Disqus


To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.



Choosing The Best Beginner's Programming Language
01/03/2017, the online publication from Red Hat, is currently conducting a poll as to which is the best programming language for beginners. This has of course generated quite a lively debate.

Android About To Overtake Windows On Internet

New figures from StatCounter reveal that, if current trends continue, Android will become the most popular operating system for internet access in the very near future.

More News


Last Updated ( Friday, 23 March 2012 )

RSS feed of news items only
I Programmer News
Copyright © 2017 All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.