Title: On the Power of Interactive Proofs for Learning
Speaker: Ninad Rajgopal (University of Cambridge)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: March 20, 2024, 14:00
Where: FCUL, C6.2.33

Video recording: https://youtu.be/ydpcPfmEJws

Abstract: Interactive proof systems for delegating computation allow a resource-constrained client (or a verifier) to outsource a computational task to a powerful, yet untrusted server (prover). The goal of such a proof system is for the client to verify the result of the task using significantly fewer resources, than performing it from scratch, by interactively exchanging messages with the server who is required to prove the correctness of its computation. Such proof systems have been ubiquitously used in theory, including computational complexity theory, as well as in practice.
In this talk, we will first introduce a model by Goldwasser, Shafer, Rothblum and Yehudayoff (2021), for delegating a learning task to a server and interactively verifying its correctness. Following this we will see delegation proof systems for problems fundamental to the study of the computational complexity of learning, that allow for highly efficient verification in comparison with performing the learning task. This is joint work with Tom Gur, Mohammad Mahdi Jahanarah, Mohammad Mahdi Khodabandeh, Bahar Salamatian, and Igor Shinkar, and will appear at STOC 2024.

Bio: I am a Postdoctoral Researcher at the University of Cambridge. My main research interests are in Theoretical Computer science and in particular, the connections across the areas of Complexity Theory, Circuit Complexity, Probabilistic Proof Systems, Learning Theory, Meta-complexity, and Pseudo-randomness.

Note: The entry was updated to include the video recording.

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.