interactive-proofs
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 7: Interactive Proofs & PCP Theorem
IP = PSPACE via arithmetization and the sum-check protocol, then the PCP theorem NP = PCP[O(log n), O(1)] — proofs checkable in O(1) bits — so approximating Max-3-SAT is NP-hard.