Interactive Proofs 姚鹏晖

Presentation on theme: "Interactive Proofs 姚鹏晖"— Presentation transcript:

1 Interactive Proofs 姚鹏晖
助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502

2 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，定义，定理，证明

3 Public coins and AM

4 Public coins and AM

5 GNI and AM

6 Finite Fields

7 Hash functions

8 Set lower bound protocol

9 Set lower bound protocol

10 Set lower bound protocol

11 GNI and AM

12 IP vs AM

13 Can GI be NP-complete

14 Interactive proof protocol for #P

15 Arithmetization

16 Interactive protocol for #P

17 Interactive protocol for #P

18 Interactive protocol for #P

19 Interactive protocol for #P

20 Permanent

21 Permanent

22 Protocol for TQBF

23 Protocol for TQBF

24 Homework 或放到计算机科学与技术楼502门口信封 (中英文不限)
Chapter 7. Exercise 8.1,8.3,8.5,8.6,8.11 作业发送给助教刘明谋 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间：12月13日10:00前