Royal Society Milner Prize Lecture: Complexity Theory
About this Event
The Royal Society 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 Ph.D. 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 covers 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 register via Eventbrite for a ticket
- You will only be able to join us in person on the day if you registered for an in person ticket on EventBrite.
- Live subtitles will be available in-person and virtually
Attending in person
- This lecture can be attended in-person at the Royal Society
- Doors will open to the public at 6.00pm GMT
Find travel and accessibility information on our website
Attending online
- The lecture will also be livestreamed here and on the Royal Society YouTube channel
- 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 soon after the event
For all enquiries, please contact [email protected]
Where is it happening?
Event Location & Nearby Stays:
USD 0.00
