In computer science we often ask: given a problem, how efficiently can we compute a solution? My work takes a different perspective, asking: if someone claims to have already computed a solution, how efficiently can we check it’s correct? This question has deep connections with many areas of theoretical computer science, including cryptography, complexity theory and quantum computing; and, more recently, has had significant practical impact in decentralised systems. In this talk I will focus on two aspects of my work in this area: first, on designing concretely efficient checking protocols; and second, on ensuring the integrity of efficient checking against quantum attackers.
Nicholas Spooner is an assistant professor at the University of Warwick, UK, which he joined in January 2021. Before that, he spent a year and a half as a postdoc at Boston University. He received his PhD from UC Berkeley in 2020. His interests lie within the union of cryptography, quantum computing, and proof systems.