After we saw several randomized algorithms for primality we needed a way to classify and analyze the power of probabilistic computation. The power of computational complexity comes from not just studying old models of computation but taking new ones and finding ways to analyze their computational power as well.
Sipser's main result showed the BPP is contained in the fourth level of the polynomial-time hierarchy and the paper also includes Gács improvement putting BPP in Σ2∩Π2. More importantly Sipser introduced new techniques into the complexity theorists' toolbox including
- A new resource-bounded Kolmogorov distinguishing complexity, and
- Using Carter-Wegman hash functions to focus randomness. Perhaps the first extractor.