Milner Prize Lecture: Highlights from 40 years of complexity theory

The Milner Prize Lecture is a free talk on complexity theory, the study of efficient computation, delivered at the Royal Society. It is given by Professor Johan Håstad, who receives the Royal Society Milner Award for his transformational impact on circuit complexity, cryptography, parallel computing and approximate optimisation. He will present classical results and highlights from 40 years of the field, covering topics such as multiplying and factorizing large integers, problems from logic and graph theory, links to cryptography, and how quantum computers might change what can be solved efficiently. The lecture can be attended in person or watched online, with live subtitles available.