CS 6520 - Computational Complexity Fall 2017
Friday, November 3, 2017
We gave the proof that co-NP and P
have interactive protocols (Arthur-Merlin games with unbounded rounds). We will generalize to PSPACE on Monday.
Algebraic methods for interactive proof systems
by Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan