# The Abel Lectures

Avi Wigderson, Professor at the School of Mathematics, Institute for Advanced Study, Princeton will be delivering this year's Science Lecture at the University of Oslo, on May 23rd. The lecture is called *Randomness and pseudorandomness*, and is one of four lectures to be held this day in connection with the Abel Prize week. The other speakers are Abel Laureate Endre Szemerédi, László Lovász and Timothy Gowers.

**Avi Wigderson**: *Randomness and pseudorandomness:*

**Abstract**

Is the universe inherently deterministic or probabilistic? Perhaps more importantly - can we tell the difference between the two?

Humanity has pondered the meaning and utility of randomness for millennia.

There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling... Indeed, randomness seems indispensable!

Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from "unpredictable" phenomena like the weather or the stock market?

Pseudorandomness is the study, by mathematicians and computer scientists, of deterministic structures which share some properties of random ones.

Understanding pseudorandom objects and constructing them efficiently leads to a surprisingly positive answers to the questions above, namely that much can be done with poor quality randomness, of even without any randomness at all. I plan to explain key aspects of this theory, and mention some of Endre Szemeredi's contributions to pseudorandomness.

The talk is aimed at a general audience, and no particular background will be assumed.

**Endre Szemerédi:*** In every chaos there is an order*

**Abstract:**

The chaos and order will be defined relative to three problems.

1. Arithmetic progressions

This part is connected to a problem of Erdős and Turán from the 1930's. Related to the van der Waerden theorem, they asked if the density version of that result also holds:

Is it true that an infinite sequence of integers of positive (lower) density contains arbitrary long arithmetic progressions?

The first result in this direction was due to K. F. Roth, who proved that any sequence of integers of positive (lower) density contains a three-term arithmetic progression.

I will give a short history of the generalization of Roth's result and explain some ideas about the "easiest"" proof.

2. Long arithmetic progression in subset sums

I will give exact bound for the size of longest arithmetic progression in subset sums. In addition, I shall describe the structure of the subset sums, and give applications in number theory and probability theory.

3. Embedding sparse graphs into large graphs

**László Lovász:** The many facets of the Regularity Lemm

**Abstract:**

The Regularity Lemma of Szemeredi, first obtained in the context of his theorem on arithmetic progressions in dense seuqences, has become one of the most important and most powerful tools in graph theory. It is basic in

extremal graph theory and in the theory of property testing. Weaker versions with better bounds (Frieze and Kannan) and stronger versions (Alon, Fisher, Krivelevich and Szegedy) have been proved and used. However, the

significance of it goes way beyond graph theory: it can be viewed as statement in approximation theory, as a compactness result for the completion of the space of finite graphs, as a result about the dimensionality of a metric space associated with a graph, as a statement in information theory. It serves as the archetypal example of the dichotomy between structure and randomness as pointed out by Tao. Its extensions to hypergraphs, a difficult problem solved by Gowers and by Rodl, Skokan and Schacht, connects with higher order Fourier analysis.

**Timothy Gowers:** The afterlife of Szemerédi’s theorem

**Abstract:**

Szemerédi's theorem asserts that every set of integers of positive upper density contains arbitrarily long arithmetic progressions. This result has been extraordinarily influential, partly because of the tools that Szemerédi introduced in order to prove it, and partly because subsequent efforts to understand the result more fully have led to progress in many other areas of mathematics, including combinatorics, ergodic theory, harmonic analysis and number theory. I shall discuss some of these later developments, to which Szemerédi himself made several essential contributions.

### The Abel Lectures

**Program**

Location: Georg Sverdrups hus, Aud. 1, University of Oslo

23 May 2012 at 10:00 - 23 May 2012 at 15:15

10.00 Welome by Pro-Rector Inga Bostad, President of The Norwegian Academy of Science and Letters Nils Chr. Stenseth, and Chair of the Abel Committee Ragni Piene.**10.10 Professor Endre Szemerédi: **"In Every Chaos There is an Order"

*11.00 Coffee/tea***11.30 Professor László Lovász: **The many facets of the Regularity Lemma"12:30 Lunch (requires registration)

**13.30 Professor Timothy Gowers:**"The afterlife of Szemerédi's theorem"

14:15 Coffee/tea

**14:30 Science Lecture: Avi Wigderson, **"Randomness and Pseudorandomness"

15.15 Ending by Chair of the Abel Committee Ragni Piene

### Yves Meyer receives the Abel Prize

The Norwegian Academy of Science and Letters has decided to award the Abel Prize for 2017 to Yves Meyer (77) of the École normale supérieure Paris-Saclay, France “for his pivotal role in the development of the mathematical theory of wavelets”. The President of the Norwegian Academy of Science and Letters, Ole M. Sejersted, announced the winner of the 2017 Abel Prize at the Academy in Oslo today, 21 March.

Yves Meyer was the visionary leader in the modern development of this theory, at the intersection of mathematics, information technology and computational science.

Wavelet analysis has been applied in a wide variety of arenas as diverse as applied and computational harmonic analysis, data compression, noise reduction, medical imaging, archiving, digital cinema, deconvolution of the Hubble space telescope images, and the recent LIGO detection of gravitational waves created by the collision of two black holes.

Yves Meyer will receive the Abel Prize from His Majesty King Harald V at an award ceremony in Oslo on 23 May.

The Abel Prize recognizes contributions of extraordinary depth and influence to the mathematical sciences and has been awarded annually since 2003. It carries a cash award of 6 million NOK (about 675,000 Euro or 715,000 USD).

(21.03.2017) More### Abel Prize announcement March 21

#### Popular science presentation by Terence Tao

The President of the Norwegian Academy of Science and Letters, Ole M. Sejersted, will announce the winner of the Abel Prize for 2017 at the Academy on the 21st of March. The Academy's choice of laureate is based on the Abel Committee's recommendation. The chair of the Abel Committee, John Rognes, will give the reasons for the awarding of the prize. The world famous mathematician Terence Tao will give the popular science presentation of the prize winner's work.

(09.03.2017) More### "Abel in Barcelona" with lecture by Louis Nirenberg

Institut d'Estudis Catalans will host the Abel in Barcelona-event on Monday the 16th of January. In connection with the final meeting of the Abel committee, whose task it is to select the Abel Prize Laureate for 2017, there will be an afternoon of lectures aimed at a broad mathematical audience. Louis Nirenberg, who shared the Abel Prize 2015 with John Nash, will give the first lecture. There will also be lectures by two of the Abel committee members, Luigi Ambrosio and Ben Green.

(04.01.2017) More### Sir Andrew J. Wiles received the Abel Prize from H.R.H. Crown Prince Haakon

Andrew Wiles received the 2016 Abel Prize from Norway's Crown Prince Haakon at an award ceremony in Oslo today, on 24 May. He receives the prize "for his stunning proof of Fermat's Last Theorem by way of the modularity conjecture for semistable elliptic curves, opening a new era in number theory", to quote the Abel Committee. The Abel Prize carries a cash award of 6 million NOK (about EUR 700,000 or USD 750,000) and has been awarded annually since 2003 by the Norwegian Academy of Science and Letters.

(24.05.2016) More### The Abel lectures 2016

Abel Laureate Sir Andrew Wiles will give his prize lecture at the University of Oslo on the 25th of May, followed by two Abel Lectures by Henri Darmon and Manjul Bhargava. Simon Singh will then give the popular lecture *From Fermat's Last Theorem to Homer's Last Theorem.*