Ahlfors Lecture series
November 13-14, 2014, Organizers: H-T Yau and S-T Yau
Harvard University, Science Center
Speaker and Program
Avi Wigderson (Institute of Advanced Study)
November 13, 2014:|
in SC Hall A
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 explain the main ideas and results of this theory.
November 14, 2014:|
in SC Hall D
| Permanent and Determinant: non-identical twins|
The determinant is undoubtedly the most important polynomial function
in mathematics. Its lesser known sibling, the permanent, plays very
important roles in enumerative combinatorics, statistical and
quantum physics, and the theory of computation. In this lecture
I plan to survey some of the remarkable properties of the permanent,
its applications and impact on fundamental computational problems,
its similarities to and apparent differences from the determinant,
and how these relate to the P vs. NP problem.
Additional talk on Nov. 14, 2014, 11:45 AM, Room 232: "Avi Wigderson: Points, Lines and Ranks of design matrices":
Abstract: The Sylvester-Gallai theorem in Euclidean geometry asserts that if a set of points has the property that
every line through two of them contains a third point (such lines are called "special"), then they must
all be on the same line, namely, 1-dimensional. There are many proofs, all elementary. When one moves
to the complex numbers, the same condition can be met in two dimensions, and Kelly's theorem asserts
that the points must lie in a 2-dimensional space. The first proof used algebraic geometry, and a
later more elementary proof of this fact is still quite complicated.
We prove several extensions and quantitative versions of these theorems (and related ones), which are
motivated by questions in several areas, including about locally correctable codes, matrix rigidity, and
arithmetic combinatorics. In these extensions the assumption about "all" lines being special, is relaxed
to having "many" special lines in the given point set. As it happens, such weaker conditions still impose
considerable structure on the point set! We also address "robust" versions in which triples of points are
only "nearly collinear".
Our results are obtained via general, tight rank lower bounds on matrices about with certain zero/non-zero pattern of entries.
The proofs use an interesting combination of combinatorial, algebraic and analytic tools. In particular, they
supply a simple new proof of Kelly's theorem.
This is a lecture series in honor of
Lars Ahlfors (1907-1996)
who was William Caspar Graustein Professor of Mathematics at
Harvard University from 1946 to 1977. Ahlfors won the fields medal in 1936 and
the Wolf prize in 1981.