Post-2002 developments that come to mind that hadn't occurred at the time of writing: anything involving Fourier analysis of the boolean hypercube, like Ryan Williams' circuit lower-bounds & the Unique Games Conjecture, and work on pseudorandomness.
More broadly, I'm always fascinated how interaction of (probabilistic) functions is the underlying concept across such a broad swath of recent developments in complexity theory. Looking forward to seeing where the next paradigm shift comes from
More broadly, I'm always fascinated how interaction of (probabilistic) functions is the underlying concept across such a broad swath of recent developments in complexity theory. Looking forward to seeing where the next paradigm shift comes from