Learning algorithm from natural proofsSpeaker: Chi-Ning
Title: Learning algorithm from natural proofs
Date: 23 Apr 2018 5:30pm-7:00pm
Location: Pierce 320
Food: Chinese food
Abstract: Carmosino, Impagliazzo, Kabanets, and Kolokolova gave a quasi-polynomial time learning algorithm (with membership queries) for AC_0[p] (CCC 2016 best paper). This is no only the first non-trivial learning algorithm for AC_0[p], but also a learning algorithm with very different framework from the previous.
In this talk, we assume no background in either natural proof or computational learning theory. We will first focus on the high-level framework, which involves hardness amplification and Nisan-Wigderson generator, and then go into the two main contributions of this work if time allows. Please find the notes attached as a reference.