Models That Prove Their Own Correctness

Speaker: Orr Paradise (Orr Paradise is a PhD student in the Theory of Computation group at UC Berkeley) Date: 14-01-2025, 2pm-3pm (BST) Location: Department of Computer Science, CS1.04, University of Warwick, Coventry, UK

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.

---

About Orr Paradise

JOrr 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 is on probabilistic proof systems and, more recently, its intersection with machine learning. Orr works with CETI, a nonprofit dedicated to deciphering sperm whale communication. He also serves as Head TA at JamCoders, a free summer camp on algorithms for high schoolers in Kingston, Jamaica.