Zero Knowledge cover image

Error Correcting Codes & Information Theory with Ron Rothblum

Zero Knowledge

00:00

The Evolution of Complexity Theory

Computational complexity theory deals with showing that some problems are hard not just to solve, but even to approximate. A tool called PCPs was introduced in the early 90s for about 20 years and has had an enormous impact throughout the years on this entire field of computational complexity theory. And IOPs, our interactive Oracle proofs, are a generalization of this notion in which it's not just like one static proof for a much eerie small number of bits,. But miraculously, we can build this kind of thing. So anyway, that was me trying to articulate this field of complexity theory.

Transcript
Play full episode

The AI-powered Podcast Player

Save insights by tapping your headphones, chat with episodes, discover the best highlights - and more!
App store bannerPlay store banner
Get the app