Interactive Proofs 姚鹏晖

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

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

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

3 Definition of NP

4 Definition of NP

5 Deterministic interactive proofs

6 Deterministic interactive proof systems

7 Deterministic interactive proof systems

8 Deterministic interactive proof systems

9 Probabilistic verifier

10 Basic properties of IP

11 Interactive proofs for graph nonisomorphism

12 Interactive proofs for graph nonisomorphism

13 Quadratic nonresiduosity

14 Interactive proofs for graph nonisomorphism

15 Zero-knowledge proofs

16 Zero-knowledge proofs for GI

17 Public coins and AM

18 Facts on MA and AM

19 Multiprover interactive proofs

20 Multiprover interactive proofs

21 Two-prover one-round game

22 Two-prover one-round game and 3SAT

23 CHSH game The God does not play dice. Albert Einstein
Bell’s Inequality

24 GNI and AM

25 Hash functions

26 Set lower bound protocol

27 Set lower bound protocol

28 Homework 或放到计算机科学与技术楼502门口信封 (中英文不限)
Chapter 7. Exercise 7.1,7.3,7.5,7.6,7.9 作业发送给助教刘明谋 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间：11月29日10:00前