Interactive Proofs 姚鹏晖 Email: pyao@nju.edu.cn 助教: 刘明谋 liu.mingmou@smail.nju.edu.cn 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502 http://tcs.nju.edu.cn/wiki/index.php/Main_Page
What we have learnt Deterministic TM and complexity classes P, PSPACE, EXP Nondeterministic TM and complexity classes NP, NEXP Polynomial hierarchy Probabilistic Turing machines and complexity classes BPP, RP, coRP, ZPP 回顾每一个item,定义,定理,证明
Definition of NP
Definition of NP
Deterministic interactive proofs
Deterministic interactive proof systems
Deterministic interactive proof systems
Deterministic interactive proof systems
Probabilistic verifier
Basic properties of IP
Interactive proofs for graph nonisomorphism
Interactive proofs for graph nonisomorphism
Quadratic nonresiduosity
Interactive proofs for graph nonisomorphism
Zero-knowledge proofs
Zero-knowledge proofs for GI
Public coins and AM
Facts on MA and AM
Multiprover interactive proofs
Multiprover interactive proofs
Two-prover one-round game
Two-prover one-round game and 3SAT
CHSH game The God does not play dice. Albert Einstein Bell’s Inequality
GNI and AM
Hash functions
Set lower bound protocol
Set lower bound protocol
Homework 或放到计算机科学与技术楼502门口信封 (中英文不限) Chapter 7. Exercise 7.1,7.3,7.5,7.6,7.9 作业发送给助教刘明谋 liu.mingmou@smail.nju.edu.cn 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间:11月29日10:00前