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 interactive proof systems and dIP=NP Interactive proof systems and complexity class IP Interactive proofs of GNI, QNR Zero-knowledge proof for GI Public-coin (Arthur-Merlin) interactive proof systems, MA, AM Multi-prover interactive proof systems MIP 回顾每一个item,定义,定理,证明
Public coins and AM
Public coins and AM
GNI and AM
Finite Fields
Hash functions
Set lower bound protocol
Set lower bound protocol
Set lower bound protocol
GNI and AM
IP vs AM
Can GI be NP-complete
Interactive proof protocol for #P
Arithmetization
Interactive protocol for #P
Interactive protocol for #P
Interactive protocol for #P
Interactive protocol for #P
Permanent
Permanent
Protocol for TQBF
Protocol for TQBF
Homework 或放到计算机科学与技术楼502门口信封 (中英文不限) Chapter 7. Exercise 8.1,8.3,8.5,8.6,8.11 作业发送给助教刘明谋 liu.mingmou@smail.nju.edu.cn 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间:12月13日10:00前