南京大学计算机软件新技术国家重点实验室 

摘 要：

通信复杂性(communication complexity)是研究分布式系统中完成一个计算任务最少需要交换多少比特信息。这是理论计算机科学的一个基础计算模型之一，也是为数不多的人们知道如何证明复杂性下界的模型。众多的复杂性下界问题都是通过规约到通信复杂性来解决。在通信复杂性模型中，量子通信可以实现无条件指数级加速。过去二十年，通过引入信息论方法，通信复杂性的一系列基础性问题获得了重大进展。在这个报告中，我将汇报下本人通过量子信息论方法研究量子通信复杂性上取得的一些成果以及面临的挑战。

报告人简介：

姚鹏晖，南京大学计算机科学与技术系副教授；本科毕业于华东师范大学数学系，博士毕业于新加坡国立大学量子技术中心（CQT），之后先后在荷兰国家数学与计算机中心（CWI）、加拿大滑铁卢大学量子计算研究所（IQC）、美国马里兰大学量子信息与计算机科学联合中心（QuICS）从事博士后研究工作。主要研究方向是计算复杂性、量子算法与量子信息论。目前，在算法和通信复杂性上做出一系列重要成果。在理论计算机科学顶级会议STOC、FOCS和信息论顶级期刊IEEE Transaction on Information Theory上发表多篇论文。2018年获得第14批中组部国家“青年千人计划”项目。

时间：4月25日星期四  12:20

地点：计算机科学技术楼111室