[Proof Complexity] MIAO seminar Wed Mar 19 at 15:30 CET with Antonina Kolokolova: Learning from proofs

[Jakob Nordström]

Dear all,

With apologies for the short forward notice, this Wednesday March 19 at 
15:30 CET (note the time!) we will have the opportunity to listen to 
Antonina Kolokolova from Memorial University presenting a seminar titled 
"Learning from proofs". You find the abstract at the bottom of this 
message.

We will run this as a hybrid seminar at the University of Copenhagen. 
Local participants are warmly welcome to seminar room N116 at 
Universitetsparken 1, while other participants are equally warmly 
welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . 
Please feel free to share this information with colleagues who you think 
might be interested. We are also hoping to record the seminar and post 
on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch 
for people who would like to hear the talk but cannot attend.

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Wednesday March 19 at 15:30 (note the time!) in seminar room N116, 
Universitetsparken 1, University of Copenhagen, and on Zoom
*Learning from proofs
*(Antonina Kolokolova, Memorial University)
/
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, we 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. I will also talk about the existence of constructive proofs, 
with complexity-theoretic consequences for some notions of "constructive".


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se