skip to content

Department of Computer Science and Technology

Date: 
Thursday, 9 January, 2025 - 14:00 to 15:00
Speaker: 
Orr Paradise (UC Berkeley)
Venue: 
Computer Laboratory, William Gates Building, FW26

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.

Seminar series: 
Algorithms and Complexity Seminar

Upcoming seminars