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
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.
NP vs P/poly
NP vs P/poly
EXP vs P/poly
Upper bounds imply lower bounds
Existence of hard functions
Existence of hard functions
Nonuniform Hierarchy Theorem
NC and AC
NC and parallel algorithms
P-completeness
Circuit lower bounds: Complexity theory’s Waterloo
ACC0
Frontiers of Circuit lower bounds
Other approaches to circuit lower bounds Decision tree complexity Ch 12 Communication complexity Ch 13 Circuit lower bounds Algebraic complexity Ch16 Proof complexity Ch15
Homework 或放到计算机科学与技术楼502门口信封 (中英文不限) Chapter 6. Exercise 6.3,6.4,6.12, 6.14,6.15, 作业发送给助教刘明谋 liu.mingmou@smail.nju.edu.cn 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间:11月8日10:00前