Started our unit on Arthur-Merlin games.
Defined AM and gave the private-coin protocol for graph non-isomorphism and informally described the public coin protocol. We'll do a detailed public-coin protocol on Friday.
- Arthur-Merlin on Wikipedia
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes by László Babai and Shlomo Moran.
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol design by Oded Goldreich, Silvio Micali and Avi Wigderson. Among other things this paper gives the first Arthur-Merlin protocol for graph isomorphism.
- Private coins versus public coins in interactive proof systems by Shafi Goldwasser and Michael Sipser
- Graph Isomorphism in Quasipolynomial Time by László Babai
