Boolean circuits 姚鹏晖 Email: pyao@nju.edu.cn 助教: 刘明谋 liu.mingmou@smail.nju.edu.cn 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502 http://tcs.nju.edu.cn/wiki/index.php/Main_Page.

Presentation on theme: "Boolean circuits 姚鹏晖 Email: pyao@nju.edu.cn 助教: 刘明谋 liu.mingmou@smail.nju.edu.cn 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502 http://tcs.nju.edu.cn/wiki/index.php/Main_Page."— Presentation transcript:

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

2 What we have learnt Boolean circuits
Complexity class P/poly, P vs. P/poly CKT-SAT is NP complete Uniformly generated circuits Turing machines with advice.

3 NP vs P/poly

4 NP vs P/poly

5 EXP vs P/poly

6 Upper bounds imply lower bounds

7 Existence of hard functions

8 Existence of hard functions

9 Nonuniform Hierarchy Theorem

10 NC and AC

11 NC and parallel algorithms

12 P-completeness

13 Circuit lower bounds: Complexity theory’s Waterloo

14 ACC0

15 Frontiers of Circuit lower bounds

16 Other approaches to circuit lower bounds
Decision tree complexity Ch 12 Communication complexity Ch 13 Circuit lower bounds Algebraic complexity Ch16 Proof complexity Ch15

17 Homework 或放到计算机科学与技术楼502门口信封 (中英文不限)
Chapter 6. Exercise 6.3,6.4,6.12, 6.14,6.15, 作业发送给助教刘明谋 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间：11月8日10:00前