近日，算法领域顶级会议ACM-SIAM Symposium of Discrete Algorithms （SODA）公布了2019年论文录用情况，交叉信息院共5篇论文被大会接收，其中1篇(2人次)来自交叉信息院研究生，4篇(5人次)来自姚班计科50。金秋九月亦是丰收季节，交叉信息院在SODA2019顶会论文收编上硕果累累，大放异彩。
5篇论文成果展示（按照理论计算机国际惯例，论文作者以字母排序，不代表贡献大小）：
Fine-grained Complexity Meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
A Faster External Memory Priority Queue with DecreaseKeys
Shunhua Jiang, Kasper Green Larsen
Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie, Hengjie Zhang
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, Yuhao Zhang
Dynamic Edge Coloring with Improved Approximation
Ran Duan，Haoqing He，Tianyi Zhang
论文成果速递：
由计科50吕凯风同学和2017届姚班校友陈立杰共同参与完成的论文《当精细复杂度遇上IP=PSPACE》研究了求P问题的精确解和近似解的复杂性。该论文在经典的IP=PSPACE证明的基础上，发现了有界空间计算过程的交互式证明和求P问题的精确或近似解的精细复杂度之间的深刻联系，并对一系列P问题给出了从精确解到近似解的归约。应用文中提出的新归约方法还可以得到最长公共子串问题的确定性近似求解的新理论瓶颈。
由计科50姜舜华同学参与完成的论文《外部存储器模型中更快的支持DecreaseKey操作的优先队列》聚焦外部存储器模型下的优先队列。优先队列是一种重要的数据结构，它维护一组有优先级的元素，并支持Insert，Delete，ExtractMin和DecreaseKey操作。该论文提出了一个在外部存储器模型下的新的支持DecreaseKey操作的优先队列来缩紧下界和上界之间的差距，其优先队列具有分摊的O(1/B log(N/B) / loglogN) I/O的期望复杂度。论文展示其研究结果改进了保持了十多年的支持DecreaseKey操作的外部存储器优先队列，并且还提供了更快的外部存储器模型下的单源最短路径算法。
由计科50张恒捷同学参与完成的论文《基于扩展图分解的分布式网络三角形检测》提出了改良版的算法来解决在CONGEST模型中寻找图中的三角形问题和其他相关问题。具体来说，该论文提出了一种创新的分布式图分解算法，并使用该算法证明了在一个图中判断是否有三角形，枚举所有三角形，计算所有三角形的数量这三个问题均能在Õ(√n)次计算内解决，增强了之前最先进的结果。作者相信该算法的实用之处远超出这项工作本身。
由计科50彭炳辉、陶润洲两位同学在第一届姚班校友、香港大学黄志毅助理教授的指导下共同参与完成的论文《一些经典算法在完全在线匹配算法的最优分析》深入研究完全在线匹配算法并且给出了经典算法的最优分析。二分图在线匹配问题是由Karp et al. 首次提出，研究的是如何在在线的情况下得到尽可能大的匹配。同时提出的Ranking算法可达到最优的近似比1-1/e。Huang et al. 首次将其拓展到了一般图上的完全在线匹配问题，证明了Ranking算法在此模型下仍可达到高于0.5的近似。这篇文章进一步研究了完全在线匹配问题并且给出了Ranking以及Water-filling这两个经典在线匹配算法的最优近似比分析。同时，这篇文章的结果也改进了关于其他一些匹配模型，比如边到达模型下的最优下界。
由我院段然助理教授（计科50班主任）指导，2013级博士生何昊青及2016级博士生张天翼共同完成的论文《边染色问题的动态近似算法》着眼于边染色问题。边染色问题是指，在一个简单无向图中，用尽量少的颜色对所有边进行染色，使得相邻的边颜色不同。在增删一条边的情形下，之前最好的边染色动态近似算法[BCHN18]，可以在O(logΔ)时间维护一个使用2Δ-1种颜色的边染色方案，这里Δ代表图中边的最大度数。该论文提出一种边染色动态近似算法，在增删一条边的情形下，可以在poly(log n)时间维护一个使用(1+ε)Δ种颜色的染色方案，其中ε为常数。
SODA 由 ACM（美国计算机协会）和 SIAM（美国工业与应用数学学会）两大国际学术组织联合主办，与 STOC、FOCS 一起被公认为是算法领域的三大顶级学术会议。
（文/谢琴）
