本周日（11月14日）晚20:00，学堂112，任翰林、高睿泉和何中天同学会分享自己的工作，时长约为一到两小时。
任翰林：Faster algorithms for distance sensitivity oracles
任翰林是姚班2016级（计科60）本科生，现在是牛津大学的博士生，导师为Prof. Rahul Santhanam。本次seminar将会介绍他在distance sensitivity oracles (DSOs)方面的工作。给定一张n个点、边权在[1, M]中的有向图G = (V, E)，我们要构造一个数据结构求解如下询问：给定一个起点u和终点v，以及一个坏掉的点或者边f，求出从u到v不经过f的最段路径长度。本次talk会展示如何用快速矩阵乘法实现一个预处理时间为O(n^{2.5794}M)、查询时间为O(1)的DSO。
高睿泉&何中天：Improved Online Correlated Selection
高睿泉和何中天是姚班2018级（计科80）本科生。本次seminar会介绍他们在在线二分图匹配方面的研究。在线二分图匹配问题是在线算法的核心问题之一。尽管带有点权的问题的早在1990年就被解决，带有边权的问题直到去年才有突破平凡下界的方法。这一方法用到Online Correlated Selection(OCS)，并已经被应用于其他的在线匹配问题上。本次talk是在上述工作的基础上提出了OCS的改进算法以及OCS的推广，并改进了相关的在线匹配问题的近似比。
Make IIIS Great Again!
