Open Lecture — In Pursuit of Structure: Why a Little Randomness (Almost) Always Helps

Perhaps somewhat counter-intuitively, many random phenomena are actually extremely well understood.  To give a basic example, when a fair coin is flipped a million times, we can predict the resulting number of heads with very high accuracy.  When attacking a mathematical problem it is therefore often useful to assume that the principal object of interest (such as a set of integers, or a graph) exhibits random or at least random-like behavior, which we understand well, before moving on to investigate what happens when this is not the case.

This general philosophy has been applied with great success for many decades.  It has been instrumental in, for instance, understanding century-old problems about patterns of prime numbers, or analyzing the structural properties of large networks.

A recent breakthrough on one such famous open problem, which can easily be explained using a card game, appears to use no randomness at all.  Instead it relies on an entirely different technique, calling our long-standing reliance on randomness into question.

Light refreshments will be served before the lecture at 3:30 p.m.