MA

1 page tagged.

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.