Skip to content

Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson

The Peterman Pod

Hosted by Ryan Peterman

2h 15m
Transcript

Original podcast

Where to listen

About this episode

Avi Wigderson is the only person in history to have won both a Turing Award (computer science) and Abel Prize (math). I interviewed him all about his field. • My ergonomic keyboard project I mentioned, you can follow along here: https://read.compose.llc/ Podcast links: • YouTube: https://youtu.be/5GUcvSAJcJw • Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835 • Transcript: https://www.developing.dev/p/turing-award-winner-p-vs-np-zero Thank you to this episode's sponsor for supporting my work: • WorkOS: makes your app Enterprise Ready with easy to use APIs to add SSO, SCIM, RBAC, and more in just a few lines of code, check them out at https://workos.com/ Timestamps: (00:00) Intro (01:08) P vs NP (14:51) What if you relaxed correctness (25:38) Why NP complete problems are equivalent (30:33) Space vs time complexity (43:06) Why people use SAT solvers (45:53) Randomness is a resource (55:48) Randomness depends on computational power (01:21:20) Zero knowledge proofs and their significance (01:38:30) Quantum computation and why it matters (01:56:24) Math vs computer science (02:08:16) Major breakthroughs and his experience (02:12:31) Advice for his younger self (02:14:48) Outro Where to find Avi: • Wikipedia: https://en.wikipedia.org/wiki/Avi_Wigderson • Personal Website: https://www.math.ias.edu/avi/home Where to find Ryan: • Newsletter: https://www.developing.dev/ • X/Twitter: https://x.com/ryanlpeterman • LinkedIn: https://www.linkedin.com/in/ryanlpeterman/ • Threads: https://www.threads.com/@ryanlpeterman • Instagram: https://www.instagram.com/ryanlpeterman • TikTok: https://www.tiktok.com/@ryanlpeterman Referenced in this episode: • PCP Theorem paper: https://www.cs.umd.edu/~gasarch/TOPICS/pcp/AS.pdf • Paper on SAT approximation hardness: https://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf • Turing's paper: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf • Original paper on NP completeness: https://www.cs.toronto.edu/~sacook/homepage/1971.pdf • Ryan William's breakthrough result on space vs time: https://people.csail.mit.edu/rrw/time-vs-space.pdf • Old result on space vs time: https://www-wjp.cs.uni-saarland.de/publikationen/HPV75.pdf • Paper describing constant space majority solution: https://people.cs.umass.edu/~barring/publications/bwbp.pdf • Fast primality test paper: https://www.sciencedirect.com/science/article/pii/0022314X80900840/pdf?md5=6f748cd82fa8efa1a637efab5f632baa&pid=1-s2.0-0022314X80900840-main.pdf • Deterministic primality test paper: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf • Randomness vs observer paper: https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/How_To_Generate_Cryptographically_Strong_Sequences_Of_Pseudo-Random_Bits.pdf • Hardness vs randomness paper: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf • Erdos original sum vs product paper: https://users.renyi.hu/~p_erdos/1983-18.pdf • Terrence Tao sum vs product paper: https://arxiv.org/pdf/math/0301343 • Seminal interactive proof paper: https://www.cs.miami.edu/home/burt/learning/csc609.221/goldwasser-micali-rackoff-knoweldge-complexity.pdf • Zero knowledge proof paper: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GMW86/GMW86.pdf • Shor's algorithm original paper: https://arxiv.org/pdf/quant-ph/9508027 • Lattice paper (new hard problems): https://dl.acm.org/doi/epdf/10.1145/258533.258604 • MIP* vs RE paper: https://arxiv.org/pdf/2001.04383 • Zero knowledge non-interactive proofs: https://eprint.iacr.org/2025/1296.pdf

Transcript

0:00
2:15:47

18,873 words · 2 speakers

Speaker names marked are inferred from speaking time and the show’s known hosts — they are not voice-verified.

Page updated · transcript and summary are machine-generated