World Model · podcast knowledge graph

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

2026-06-01 · 136 min · 40 entities

episode page audio

Asserted relationships

  • → references Science concept
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://sciencedirect.com/science/article/pii/0022314X80900840/pdf?md5=6f748cd82fa8efa1a637efab5f632baa&pid=1-s2.0-0022314X80900840-main.pdf
  • → references math concept
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://arxiv.org/pdf/math/0301343
  • → references Avi Wigderson person
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://en.wikipedia.org/wiki/Avi_Wigderson
  • → references Quant Ph person
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://arxiv.org/pdf/quant-ph/9508027
  • → hosted by Ryan Peterman person
    0.55
    evidence rules-v5
    Feed author/publisher: Ryan Peterman
  • → discusses Technology company
    0.40
    evidence rules-v5
    Feed category: Technology
  • → references Publications website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://people.cs.umass.edu/~barring/publications/bwbp.pdf
  • → references developing.dev website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://developing.dev/
  • → references @Ryanlpeterman website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://tiktok.com/@ryanlpeterman
  • → references read.compose.llc company
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://read.compose.llc/
  • → references workos.com website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://workos.com/
  • → references Homepage website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.toronto.edu/~sacook/homepage/1971.pdf
  • → references Epdf website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://dl.acm.org/doi/epdf/10.1145/258533.258604
  • → references Turing Award Winner P Vs Np Zero website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://developing.dev/p/turing-award-winner-p-vs-np-zero
  • → references ~Gasarch website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.umd.edu/~gasarch/TOPICS/pcp/AS.pdf
  • → references Turing Paper person
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.virginia.edu/~robins/Turing_Paper_1936.pdf
  • → references Time Vs Space person
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://people.csail.mit.edu/rrw/time-vs-space.pdf
  • → references Publikationen website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://www-wjp.cs.uni-saarland.de/publikationen/HPV75.pdf
  • → references Primality V6 website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
  • 0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.miami.edu/home/burt/learning/csc609.221/goldwasser-micali-rackoff-knoweldge-complexity.pdf

Entities found in this episode

websites 20

  • mentioned Publications website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://people.cs.umass.edu/~barring/publications/bwbp.pdf
  • mentioned developing.dev website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://developing.dev/
  • mentioned @Ryanlpeterman website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://threads.com/@ryanlpeterman
  • mentioned workos.com website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://workos.com/
  • mentioned Homepage website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.toronto.edu/~sacook/homepage/1971.pdf
  • mentioned Epdf website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://dl.acm.org/doi/epdf/10.1145/258533.258604
  • 0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://developing.dev/p/turing-award-winner-p-vs-np-zero
  • mentioned ~Gasarch website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.umd.edu/~gasarch/TOPICS/pcp/AS.pdf
  • mentioned Publikationen website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://www-wjp.cs.uni-saarland.de/publikationen/HPV75.pdf
  • mentioned Primality V6 website
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
  • references Publications website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://people.cs.umass.edu/~barring/publications/bwbp.pdf
  • references developing.dev website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://developing.dev/
  • references @Ryanlpeterman website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://tiktok.com/@ryanlpeterman
  • references workos.com website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://workos.com/
  • references Homepage website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.toronto.edu/~sacook/homepage/1971.pdf
  • references Epdf website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://dl.acm.org/doi/epdf/10.1145/258533.258604
  • 0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://developing.dev/p/turing-award-winner-p-vs-np-zero
  • references ~Gasarch website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.umd.edu/~gasarch/TOPICS/pcp/AS.pdf
  • references Publikationen website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://www-wjp.cs.uni-saarland.de/publikationen/HPV75.pdf
  • references Primality V6 website
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

persons 12

  • mentioned Avi Wigderson person
    0.90
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://en.wikipedia.org/wiki/Avi_Wigderson
  • mentioned Quant Ph person
    0.90
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://arxiv.org/pdf/quant-ph/9508027
  • references Avi Wigderson person
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://en.wikipedia.org/wiki/Avi_Wigderson
  • references Quant Ph person
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://arxiv.org/pdf/quant-ph/9508027
  • mentioned Ryan Peterman person
    0.70
    evidence rules-v5
    Feed author/publisher: Ryan Peterman
  • hosted by Ryan Peterman person
    0.55
    evidence rules-v5
    Feed author/publisher: Ryan Peterman
  • mentioned Turing Paper person
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.virginia.edu/~robins/Turing_Paper_1936.pdf
  • mentioned Time Vs Space person
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://people.csail.mit.edu/rrw/time-vs-space.pdf
  • 0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.miami.edu/home/burt/learning/csc609.221/goldwasser-micali-rackoff-knoweldge-complexity.pdf
  • references Turing Paper person
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.virginia.edu/~robins/Turing_Paper_1936.pdf
  • references Time Vs Space person
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://people.csail.mit.edu/rrw/time-vs-space.pdf
  • 0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://cs.miami.edu/home/burt/learning/csc609.221/goldwasser-micali-rackoff-knoweldge-complexity.pdf

concepts 4

  • mentioned Science concept
    0.90
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://sciencedirect.com/science/article/pii/0022314X80900840/pdf?md5=6f748cd82fa8efa1a637efab5f632baa&pid=1-s2.0-0022314X80900840-main.pdf
  • mentioned math concept
    0.90
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://arxiv.org/pdf/math/0301343
  • references Science concept
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://sciencedirect.com/science/article/pii/0022314X80900840/pdf?md5=6f748cd82fa8efa1a637efab5f632baa&pid=1-s2.0-0022314X80900840-main.pdf
  • references math concept
    0.77
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://arxiv.org/pdf/math/0301343

companys 4

  • mentioned Technology company
    0.50
    evidence rules-v5
    Feed category: Technology
  • mentioned read.compose.llc company
    0.45
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://read.compose.llc/
  • discusses Technology company
    0.40
    evidence rules-v5
    Feed category: Technology
  • references read.compose.llc company
    0.38
    evidence rules-v5
    Link in episode "Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson": https://read.compose.llc/
Episode description as stored
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