Main
Home
/
Tags
/
linearity-testing
linearity-testing
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.