Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson
Notas do episódio
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