Randomized computation

Presentation on theme: "Randomized computation"— Presentation transcript:

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

2 What we have learnt Boolean circuits and complexity class P/poly
Polynomial hierarchy Probabilistic Turing machines and complexity classes BPP, RP, coRP, ZPP BPP algorithms for Median, PRIMES, PIT, PERFECT MATCHING Error reduction General random choices vs. fair random coins 回顾每一个item，定义，定理，证明

3 Unified definitions 概括这些的区别， what is coBPP?

4 Unified definitions

5 Unified definitions

6 BPP vs. P/poly 这个 r_0 很难找，所以这个证明并不表明BPP 存在多项式时间算法

7 BPP vs. PH

8 BPP vs. P/poly

9 BPP vs. P/poly

10 Hierarchy theorem and complete problems?
Syntactic 存在，任意 Semantic 不能用纯逻辑语句来表示

11 Randomized reductions

12 Randomized space-bounded computation

13 Random walk on graphs

14 Random walk on graphs

15 Random walk on graphs

16 Randomness-efficient repetitions: a glimpse to derandomization

17 Randomness-efficient repetitions: a glimpse to derandomization

18 Hardness vs. Randomness

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