Randomized computation 姚鹏晖 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 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,定义,定理,证明
Unified definitions 概括这些的区别, what is coBPP?
Unified definitions
Unified definitions
BPP vs. P/poly 这个 r_0 很难找,所以这个证明并不表明BPP 存在多项式时间算法
BPP vs. PH
BPP vs. P/poly
BPP vs. P/poly
Hierarchy theorem and complete problems? Syntactic 存在,任意 Semantic 不能用纯逻辑语句来表示
Randomized reductions
Randomized space-bounded computation
Random walk on graphs
Random walk on graphs
Random walk on graphs
Randomness-efficient repetitions: a glimpse to derandomization
Randomness-efficient repetitions: a glimpse to derandomization
Hardness vs. Randomness
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前