本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来梁敬勋同学和袁无为同学的报告。两场报告分别与紧凑数据结构和动态图算法相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。
报告 1 摘要
梁敬勋是姚班 2020 级（计科02）本科生。本次 seminar 他将介绍他与普林斯顿大学的俞华程老师以及计科 02 两位同学合作的工作“Dynamic Succincter”。紧凑数据结构（succinct data structures）研究如何在保持数据结构时间效率的前提下提升其空间效率。此前人们已经有一套比较普遍的方法用于构造静态的紧凑数据结构。本篇工作推广了这套方法，使其能应用在动态的数据结构上，从而改进了一系列动态紧凑数据结构的效率。该论文发表于 FOCS 2023。论文链接：https://arxiv.org/pdf/2309.12950
报告 2 摘要
袁无为是姚班 2020 级本科生，他的主要研究方向是图算法。本次 seminar 他将带来关于动态图算法（dynamic graph algorithms）的教程讲座（tutorial session）。许多经典的图问题及对应的算法都是针对静态问题设计的，但由于近些年许多使用动态图算法解决静态图问题的框架被设计出来，动态图问题及其算法便得到了越来越多关注。本教程面向零基础的同学，介绍近些年动态图的代表性算法及其核心思想，尤其是乘法权重更新算法（multiplicative weight update）和扩张图（expanders）。
欢迎全体同学参加~
Make IIIS Great Again!
