本周六下午 15:00-16:00，我们将线下给大家带来梁敬勋学长的报告。报告内容与 TCS 相关。
报告摘要
梁敬勋是卡内基梅隆大学 (CMU) 理论计算机方向的二年级博士生，研究经典数据结构的理论上界与下界，导师为 William Kuszmaul 和 Ryan O’Donnell。他本科毕业于清华大学姚班。
随机探查（uniform probing）和线性探查（linear probing）是两种最经典的哈希表方案。教科书中对它们的分析，通常依赖于定期重构整个数据结构这一假设。而它们的稳定版本，也即在操作过程中不允许重排或重构已有元素，看起来很简单，却长期缺乏有效的分析方法。
我们的工作给出了一个出人意料的答案：在允许重构的经典模型下，随机探查的性能严格优于线性探查；但在稳定模型中，情况恰好相反。稳定线性探查仍然可以保证单次操作的常数期望时间，而稳定随机探查则在一些精心构造的操作序列下，其单次操作的期望时间会增长到一个大多项式。
欢迎全体同学参加~
【重复一遍时间地点】北京时间本周六 12 月 27 日下午 15:00 - 16:00 清华学堂112 点击此处进行时区转换 腾讯会议 497-860-971
Make IIIS Great Again!
