“青年学者论坛”学术报告（3） 题 目： 数据结构复杂性理论：经典模型与新挑战 报告人： 尹一通 博士 时 间： 2010年5月13日 (星期四) 14:30-16:30 地 点： 蒙民伟楼109 摘要：数据结构复杂性理论目前面临着两方面的问题：经典理论对于数据结构中的计算的研究尚不完备；新体系结构上的数据结构应用为数据结构的经典模型带来了新的挑战。本报告将按照这两条线索进行。关于经典理论，我们刻画了数据结构的非确定(nondeterministic)复杂度，并讨论非确定数据结构复杂度在现实中的意义。我们证明了非确定复杂度意义下的数据结构难解问题的存在性，这回答了Peter Bro Miltersen于1999年提出的猜想。关于新体系结构，我们将探讨并行体系结构中，负载均衡对数据结构复杂度的影响。在查询为均均分布的前提下，提出负载均衡和复杂度同时达到最优的数据结构；在查询分布未知的前提下，证明数据结构的复杂度和负载均衡不可能同时达到最优。最后，对MapReduce中的数据分配问题，我们提出了高效的近似算法。
报告人简介 尹一通 博士，1999年至2003年期间就读于南京大学计算机科学与技术系，2003年获得理学学士学位，同年获得耶鲁大学全额奖学金资助。于2003年至2009年期间在耶鲁大学计算机科学系攻读博士学位，研究方向理论计算机科学。2009年获得计算机科学专业哲学博士学位，同年回到母校南京大学任教。目前从事理论计算机科学方面的研究，主要研究方向包括数据结构复杂性理论，随机算法。
|
| 今天是： |
