Description
Join us for the Royal Society Milner Prize Lecture delivered by Professor Johan Håstad.
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.
About the Royal Society
The Royal Society is a Fellowship of many of the world's most eminent scientists and is the oldest scientific academy in continuous existence.
https://royalsociety.org/
Subscribe to our YouTube channel for exciting science videos and live events. https://www.youtube.com/royalsociety
Find us on:
Bluesky: https://bsky.app/profile/royalsociety.org
Facebook: https://www.facebook.com/theroyalsociety/
Instagram: https://www.instagram.com/theroyalsociety/
LinkedIn: https://www.linkedin.com/company/the-royal-society
TikTok: https://www.tiktok.com/@royalsocietyscience