Probabilistically checkable proofs (PCPs) have disrupted complexity theory, most famously due to their implications to inapproximability. In a surprising turn of events, the tools used to construct efficient PCPs turned out to be the most efficient and mathematically sound approach to solving the scalability problem for blockchains, saving billions of dollars for blockchain users. Along this interesting path, old computational models — like the MIP (multiprover interactive proofs) and lesser known IOP (interactive oracle proofs) models — found rekindled interest; classical algorithms (like the fast Fourier transform) were repurposed into new interactive protocols; and algebraic coding results (like the Guruswami-Sudan list-decoding algorithm) found surprising applications to the soundness analysis of STARKs (Scalable, Transparent ARguments of Knowledge).
Eli Ben-Sasson is a co-founder and president of StarkWare, and chairman of its Board of Directors. He has been researching cryptographic and zero-knowledge proofs of computational integrity ever since he received his PhD in theoretical computer science from the Hebrew University in 2001. Eli is a co-inventor of the STARK, FRI, and Zerocash protocols and a founding scientist of the Zcash Company. Over the years, he has held research positions at Harvard, MIT, and the Institute for Advanced Study, and most recently was a professor of computer science at Technion, which he left to co-found StarkWare.
Theoretically Speaking is a lecture series highlighting exciting advances in theoretical computer science for a broad general audience. Events are free and open to the public, with first-come, first-served seating. No special background is assumed. Registration is required. This lecture will be viewable thereafter on this page and on our YouTube channel.
Light refreshments will be provided before the talk.
Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials.
If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.
All scheduled dates:
No Upcoming activities yet