A&C Seminar: Igor Oliveira "Extracting computational hardness from classical and quantum learning algorithms"

Abstract: I will explain how to obtain a hard computational problem from a non-trivial learning algorithm for a circuit class C. Results of this form can be interpreted in different ways. For an optimist, they offer a path to breakthroughs in complexity theory via the discovery of slightly better algorithms. On the other hand, for a pessimist, they might serve as an explanation for the difficulty of designing and analyzing learning algorithms for more expressive classes of functions, even in the quantum setting. The talk will provide an accessible introduction to results of this form and cover some ideas from a joint work with Srinivasan Arunachalam, Alex Grilo, Tom Gur, and Aarthi Sundaram (https://arxiv.org/abs/2012.01920).