本周六下午 15:00-17:00，我们将线下给大家带来周任飞学长和姜舜华学姐的报告。报告内容与 TCS 相关。
报告 1 摘要
周任飞是 CMU 理论计算机方向的二年级博士生，导师是 William Kuszmaul 和 Guy Blelloch。他本科毕业于清华姚班。其主要研究方向是经典数据结构，尤其是哈希表和空间高效数据结构。他也从事快速矩阵乘法方面的研究工作。
标题：数据结构中的「1 + 1 < 2」现象。我们证明了一种神奇的现象：有两个完全独立的数据结构问题 A 和 B，将它们一起解决比起将 A 和 B 分开解决有空间效率更高的解法。为了证明这种现象，我们确定并证明了检索数据结构（retrieval data structures）的最优时间、空间效率。这些成果在静态字典问题（static dictionaries）中有重要应用。
报告 2 摘要
姜舜华目前是苏黎世联邦理工学院（ETH Zurich）理论研究所（Institute for Theoretical Studies）的 Junior Fellow。此前，她在哥伦比亚大学获得博士学位，师从 Omri Weinstein 教授和 Alexandr Andoni 教授；本科毕业于清华大学姚班。她的主要研究方向包括优化算法与数据结构。
线性规划（Linear Programming，LP）是一个基础性的优化问题，在科学、工程和商业等领域中具有广泛应用。求解线性规划最常用的算法之一是内点法（Interior Point Methods，IPM），该方法在理论和实践中都具有快速收敛的优点。
在本次报告中，我们将综述近年来在线性规划内点法方面的一些最新理论进展。我们将展示如何利用动态数据结构来降低内点法单次迭代的计算成本，从而得到用于一般线性规划的更快且近乎最优的求解算法。此外，我们还将简要回顾在最大流问题及其他图问题（它们是线性规划的重要特殊情形）上的最新进展，这些成果基于内点法框架并结合了高效的图数据结构。
这些结果所使用的关键技术包括：能够利用内点法所具有的稳定性与鲁棒性保证的专用矩阵与图数据结构，以及诸如随机映射（sketching）和抽样（sampling）等随机化降维技术。
欢迎全体同学参加~
【重复一遍时间地点】北京时间本周六 12 月 20 日下午 15:00 - 17:00 清华学堂112 点击此处进行时区转换 腾讯会议 408-418-396
Make IIIS Great Again!
