Milner Prize Lecture: Highlights from 40 years of Complexity Theory
Join us for ºìÌÒÊÓƵ Milner Prize Lecture delivered by Professor Johan Håstad.
ºìÌÒÊÓƵ Milner Award and Lecture is awarded Professor Johan Håstad for the sustained and transformational impact in multiple fields, including circuit complexity, cryptography, parallel computing and approximate optimisation.
The goal of Complexity Theory is to study efficient computation. In other words, to distinguish computational problems that can be solved efficiently from those requiring too large resources to be executed on an existing computer. In the last 40 years there has been progress both in the form of discovery of new efficient algorithms but also in the form of better understanding what makes a problem difficult to solve.
Professor Håstad will give some classical results and discuss highlights from the area in general that has appeared during his long career. Problems addressed will include multiplication of large integers, factorization of integers, and problems from logic and graph theory. He will also mention how this relates to cryptography and briefly discuss how the construction of quantum computers might affect what problems can be solved efficiently.
Johan Håstad was born in 1960 and received his Bachelor of Science from Stockholm University in 1981, a Licentiate degree from Uppsala University in 1984, and his PhD from MIT in 1986. He was appointed Associate Professor at the Royal Institute of Technology in Stockholm, Sweden in 1988, advanced to the level of Professor in 1992 and has remained in this position to this date. Professor Håstad was elected a member of the Swedish Royal Academy of Sciences in 2001 and is a fellow of the American Mathematics Society (AMS) and of the Association of Computing Machinery (ACM).
He has received a number of prizes and awards and in particular the ACM Dissertation Award in 1986, the Gödel prize in 1994 and 2011 and the Knuth prize in 2018. His research interests cover many areas of Complexity theory and over the years he has made contributions to Circuit Complexity, Cryptography, Approximability of NP-hard optimization, and Proof Complexity.
Attending the event
- The event is free to join, please for a ticket
- Live subtitles will be available in-person and virtually
Attending in person
- This lecture can be attended in-person at ºìÌÒÊÓƵ
- Doors will open to the public at 6pm GMT
Find travel and accessibility information our website.
Attending online
- The lecture will also be livestreamed on this page and on the
- You can take part in the live Q&A via Slido
- This event will be recorded (including the live Q&A) and the recording will be available on YouTube shortly after the event
For all enquiries, please contact: awards@royalsociety.org.