Structure-versus-randomness in combinatorics and complexity
What does it mean for an object to look random? How can its level of randomness be measured? Seminal work of Chung, Graham and Wilson gave satisfactory answers when the objects are dense graphs, in which case the number of four-cycles can serve as a measure.
In this talk I will discuss another answer to these questions in a setting related to a famous 1975 result of Szemerédi, which says that any dense subset of the positive integers must contain arbitrarily long arithmetic progressions. In a spectacular new proof of Szemerédi's theorem, Gowers introduced a measure of randomness for functions on finite abelian groups in the form of norms, now called the Gowers uniformity norms. These norms have the extremely useful property that a truly random function will typically have a tiny uniformity norm, while any (bounded) function with a large uniformity norm must necessarily have a lot of "structure".
I will also discuss the relevance of this structure to refinements of Szemerédi's theorem that resulted from a famous ergodic-theoretic proof of Furstenburg, and how similar ideas appear in the study of quantum-versus-classical computational complexity.
Science Park 904, Room A1.04