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