Turing Award and Abel Prize winner Avi Wigderson discusses the foundational questions of theoretical computer science in a wide-ranging interview. Topics include the P vs NP problem and why most human endeavors involve NP problems, NP-completeness and reductions between problems, the PCP theorem and hardness of approximation, space vs time complexity trade-offs including Ryan Williams' recent breakthrough showing any computation in time T can be simulated in square root of T space, why SAT solvers are practical despite worst-case hardness, randomness as a computational resource and the concept of pseudorandomness, the relationship between hardness assumptions and derandomization (P=BPP), zero-knowledge proofs, and quantum computation.
10.3K Impressions