MIAO/BARC talk by Antonina Kolokolova

Wednesday, March 19, 2025, Antonina Kolokolova, Associate Professor at the Memorial University of Newfoundland, Canada, will give a talk on "Learning from Proofs".

Abstract: 
A proof often gives us more than establishing a fact: it can give us algorithms. The hidden power of constructive proofs of both hardness and easiness of computational tasks is that they give us ways to construct circuits and other computational objects: they give us learning algorithms. In this talk, she will cover several ways in which proofs of upper and lower bounds in computational complexity lead to learning algorithms, both from constructive proofs of hardness of cryptographic primitives, and from formalizing complexity statements in bounded arithmetic. Antonina will also talk about the existence of constructive proofs, with complexity-theoretic consequences for some notions of "constructive".

Bio:
Antonina Kolokolova is a faculty member in the Computer Science Department at the Memorial University of Newfoundland (Canada). She obtained her PhD in 2005 from the University of Toronto, under the supervision of Stephen Cook. Before taking her current position, Antonina was a postdoctoral researcher at the Mathematical Institute of the Academy of Sciences in the Czech Republic, and at Simon Fraser University (Canada). Her main research interests are in theoretical computer science, in particular, computational complexity theory, mathematical logic and proof complexity.

Host: Susanna de Rezende