The Founder

 

GÖRAN GUSTAFSSON Lectures in Mathematics


May 19 - 23, 2017
KTH, Stockholm

Avi Wigderson
Institute for Advanced Study, Princeton

Abstracts:

 

 

Lecture 1: Randomness
Friday, May 19, 1.15-2.15 pm
Lecture hall D1, Lindstedtsvägen 17

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?

A computational theory of randomness, developed in the past three decades, reveals (perhaps counter-intuitively) that very little is lost in such deterministic or weakly random worlds. In the talk I'll discuss the main ideas and results of this theory, give a mathematical definition of pseudorandomness, and explain how both the Riemann Hypothesis and the P vs. NP question (among others) naturally fit in this framework.

The talk is aimed at a general scientific audience.

Coffee is served between 12.45 and 13.15 outside the lecture hall.

 

Lecture 2: Operator scaling - theory and applications
Monday, May 22, 1.15-2.15 pm
Lecture hall E3, Osquars backe 14

In this talk I will explain the ``singularity problem'' for symbolic matrices over non commuting variables, and describe its myriad origins and incarnations in commutative and non-commutative algebra, computational complexity, optimization, quantum information theory, Brascamp-Lieb inequalities and other areas. I will describe the ``Operator scaling'' algorithm, which efficiently solves all these related problems, and how its analysis combines ideas from these areas. This algorithm efficiently solves a large family of non-convex optimization problems, and will hopefully find other applications.

I will elaborate on algebraic and analytic aspects of this work (respectively) in the two following lectures on May 23 and May 24. Based on joint works with Ankit Garg, Leonid Gurvits and Rafael Olivera.

 

Lecture 3: Commutative and non-commutative rank of symbolic matrices
Tuesday, May 23, 1.15-2.15 pm
Lecture hall E3, Osquars backe 14

Our object of study are matrices whose entries are linear forms in a given set of variables. We will be interested in their rank, both when variables commute and when they do not. I will discuss the importance of understanding these objects in arithmetic complexity, algebra and combinatorics, and present some structural and computational results and open problems about them.

No prior knowledge from previous talks will be assumed. Based on joint works with Ankit Garg, Leonid Gurvits and Rafael Olivera.

 

 

Sponsored by the Göran Gustafsson Foundation

2017-05-02