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/

𝗣𝗼𝗱𝗰𝗮𝘀𝘁 𝗹𝗶𝗻𝗸𝘀:

• 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

𝗧𝗵𝗮𝗻𝗸 𝘆𝗼𝘂 𝘁𝗼 𝘁𝗵𝗶𝘀 𝗲𝗽𝗶𝘀𝗼𝗱𝗲'𝘀 𝘀𝗽𝗼𝗻𝘀𝗼𝗿 𝗳𝗼𝗿 𝘀𝘂𝗽𝗽𝗼𝗿𝘁𝗶𝗻𝗴 𝗺𝘆 𝘄𝗼𝗿𝗸:

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

𝗧𝗶𝗺𝗲𝘀𝘁𝗮𝗺𝗽𝘀:

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

𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗔𝘃𝗶:

• Wikipedia: https://en.wikipedia.org/wiki/Avi_Wigderson

• Personal Website: https://www.math.ias.edu/avi/home

𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗥𝘆𝗮𝗻:

• 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

𝗥𝗲𝗳𝗲𝗿𝗲𝗻𝗰𝗲𝗱 𝗶𝗻 𝘁𝗵𝗶𝘀 𝗲𝗽𝗶𝘀𝗼𝗱𝗲:

• 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