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

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-zeroThank 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) OutroWhere to find Avi:• Wikipedia: https://en.wikipedia.org/wiki/Avi_Wigderson• Personal Website: https://www.math.ias.edu/avi/homeWhere 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/@ryanlpetermanReferenced 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