FDS Special Seminar
Orr Paradise, University of California, Berkeley
Title: Models that prove their own correctness
Host: Ruzica Piskac
Add To: Google Calendar | Outlook | iCal File
Webcast: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=beb13fd4-37b5-444b-a499-b22500f663b8
Abstract: This talk introduces Self-Proving models, a new class of models that formally prove the correctness of their outputs via an Interactive Proof system. After reviewing some related literature, I will formally define Self-Proving models and their per-input (worst-case) guarantees. I will then present algorithms for learning these models and explain how the complexity of the proof system affects the complexity of the learning algorithms. Finally, I will show experiments where Self-Proving models are trained to compute the Greatest Common Divisor of two integers, and to prove the correctness of their results to a simple verifier. No prior knowledge of autoregressive models or Interactive Proofs will be assumed of the listener. This is a joint work with Noga Amit, Shafi Goldwasser, and Guy Rothblum.
Speaker bio: Orr Paradise is a PhD student in the Theory of Computation group at UC Berkeley, where he is advised by Shafi Goldwasser and Avishay Tal. Before this, he completed his MSc at the Weizmann Institute of Science under the supervision of Oded Goldreich. His research focuses on theoretical computer science and algorithmic analysis. Beyond academia, Orr works with CETI, a nonprofit dedicated to deciphering sperm whale communication, where he contributes theoretical analysis. He also serves as Head TA at JamCoders, a free summer camp that teaches algorithms to high school students in Kingston, Jamaica.
Website: https://people.eecs.berkeley.edu/~orrp/