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

Speaker: Igor Oliveira , University of Warwick, UK

Date: Wednesday, April 20, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location:

Event Type: Seminar

Room Description:

Host:

Contact: Rahul Ilango, rilango@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: 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).

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2022.

Created by Rahul Ilango at Saturday, April 16, 2022 at 10:05 AM.