Avi Wigderson

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:

Lecture I
4:15-5:15 PM
in SC Hall A 		Randomness
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:

Lecture II
4:15-5:15 PM
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.


Lars Ahlfors
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.




History:

 Ahlfors Lecture Series, 2009 Ahlfors Lecture Series, 2010 Ahlfors Lecture Series, 2011 Ahlfors Lecture Series, 2012 Ahlfors Lecture Series, 2013