BPP

Computer science / Coursework / Randomized algorithms Lecture 3: Models & Complexity Classes Las Vegas vs Monte Carlo, the amplification gap that splits BPP from PP, the class zoo (RP/ZPP/PP/BPP), and why a weak δ-random source is secretly as good as a perfect one. Computer science / Coursework / Randomized algorithms Lecture 6: Complexity II Randomness in the verifier: BPP low in the polynomial hierarchy (Sipser–Gács); a prover + coin-flipping verifier captures PSPACE (IP=PSPACE via arithmetization, SumCheck); and, made local, PCP. Computer science / Coursework / Randomized algorithms Lecture 8: Derandomization Removing randomness while keeping the speed: enumeration, non-uniform advice, conditional probabilities with pessimistic estimators, k-wise independence, and PRGs (Nisan–Wigderson).