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-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