LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
On SNARGs for NP and Nullstellensatz Proofs
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

On SNARGs for NP and Nullstellensatz Proofs

81 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Alex Lombardi, a cryptographer at Princeton University, presents this Institute for Advanced Study seminar on whether succinct non-interactive arguments (SNARGs) can be built for all of NP under standard cryptographic assumptions. He lays out a candidate non-adaptive SNARG construction and proves its soundness two ways: first under the learning with errors assumption, or alternatively under bilinear maps, and second under a new mathematical conjecture bounding the coefficient size of Nullstellensatz proofs for membership in a specific polynomial ideal, building on Potechin and Zhang's 2024 work. Lombardi walks through the construction itself, the security analysis connecting cryptographic hardness to this algebraic conjecture, and the current state of evidence for and against the conjecture. The talk is based on joint work with Lali Devadas, Sam Hopkins, Yael Kalai, Pravesh Kothari, and Surya Mathialagan, and sits at the intersection of computational complexity, cryptography, and real algebraic geometry.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime1 h 21 m
Compared with Computer ScienceLonger than 74%
Source channelInstitute for Advanced Study (YouTube)