Cook's theorem was 1971, and I think that's a foundational result. Then there's Håstad's work from the 1980s-2010s on lower bounds and optimal non-approximabil

Cook's theorem was 1971, and I think that's a foundational result. Then there's Håstad's work from the 1980s-2010s on lower bounds and optimal non-approximability results. There's Sanjeev Arora, who was one of the guys who worked on the PCP theorem and who has now been writing interesting things about ML. There's Razborov and Rudich, with natural proofs, which was in 1994. There's Khot, who would be up with these guys provided that the UGC is true.