Colloquium information

Joint Mathematics Colloquium (ICMAT-UAM-UC3M-UCM)

Randomness and structure in combinatorics, analysis and computer science

Speaker:  Jop Briët (CWI, Amsterdam)
Date:  Friday, 24 March 2023 - 11:00
Place:  Salón de Grados del Edificio Padre Soler, Universidad Carlos III de Madrid, Campus de Leganés (*)


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. Answers to this question also arose in proofs of a famous 1975 result of Szemerédi, showing that dense subsets of the integers always contain arbitrarily long arithmetic progressions. A proof of 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." This exposes what is now often referred to as a structure-versus-randomness phenomenon. In this talk, I will discuss these notions of randomness and structure-versus-randomness and how they appear in some areas of theoretical computer science and quantum information theory. 


(*) Cómo llegar

More information: