博士前沿课程-计算复杂性理论

主讲人：

傅育熙，1992年获英国曼彻斯特大学计算机博士学位，1994年起在上海交通大学任职，历任计算机系主任，软件学院院长。是国家杰出青年基金获得者、上海市优秀学科带头人。研究领域为理论计算机科学，内容涉及程序理论、并发理论、等价性验证、可达性理论、交互理论等。学术兼职有：上海高校软件理论研究中心主任、国务院学位委员会第六届学科评议组成员 (2010-2014)、上海市计算机学会理事长 (2015-2018）、教育部计算机类专业教学指导委员会副主任 （2013-2017，2018-2022）。是Mathematical Structuresin Computer Science期刊的编委。傅育熙讲授的 《计算复杂性理论》课程获得“2019年度高校计算机专业优秀教师奖励计划”。

课程包含两部分：一、随机计算与去随机，主要内容包括：随机算法、概率图灵机与BPP、通用哈希函数族、随机游走、扩张图及其显式构造、Reigold定理。二、交互证明系统，主要内容包括：私币交互证明系统、公币交互证明系统、两类交互证明系统的等价性、IP=PSPACE、多证明者交互证明系统。
参考教材：《计算复杂性理论》（傅育熙著、清华大学出版社，2023年）。

上课时间：

17-17周，星期一第3-4节 第5-6节

星期二第3-4节第5-6节

星期三第3-4节 第5-6节

星期四第3-4节 第5-6节

星期五第1-4节

上课地点：立人楼A108