交叉信息院5篇論文被SODA2019接收
交叉信息院5篇論文被SODA2019接收
2018年09月30日 瀏覽次數: 0
近日，算法領域頂級會議ACM-SIAM Symposium of Discrete Algorithms （SODA）公布了2019年論文錄用情況，交叉信息院共5篇論文被大會接收，其中1篇(2人次)來自交叉信息院研究生，4篇(5人次)來自姚班計科50。金秋九月亦是豐收季節(jié)，交叉信息院在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證明的基礎上，發(fā)現了有界空間計算過程的交互式證明和求P問題的精確或近似解的精細復雜度之間的深刻聯(lián)系，并對一系列P問題給出了從精確解到近似解的歸約。應用文中提出的新歸約方法還可以得到最長公共子串問題的確定性近似求解的新理論瓶頸。
由計科50姜舜華同學參與完成的論文《外部存儲器模型中更快的支持DecreaseKey操作的優(yōu)先隊列》聚焦外部存儲器模型下的優(yōu)先隊列。優(yōu)先隊列是一種重要的數據結構，它維護一組有優(yōu)先級的元素，并支持Insert，Delete，ExtractMin和DecreaseKey操作。該論文提出了一個在外部存儲器模型下的新的支持DecreaseKey操作的優(yōu)先隊列來縮緊下界和上界之間的差距，其優(yōu)先隊列具有分攤的O(1/B log(N/B) / loglogN) I/O的期望復雜度。論文展示其研究結果改進了保持了十多年的支持DecreaseKey操作的外部存儲器優(yōu)先隊列，并且還提供了更快的外部存儲器模型下的單源最短路徑算法。
由計科50張恒捷同學參與完成的論文《基于擴展圖分解的分布式網絡三角形檢測》提出了改良版的算法來解決在CONGEST模型中尋找圖中的三角形問題和其他相關問題。具體來說，該論文提出了一種創(chuàng)新的分布式圖分解算法，并使用該算法證明了在一個圖中判斷是否有三角形，枚舉所有三角形，計算所有三角形的數量這三個問題均能在?(√n)次計算內解決，增強了之前最先進的結果。作者相信該算法的實用之處遠超出這項工作本身。
由計科50彭炳輝、陶潤洲兩位同學在第一屆姚班校友、香港大學黃志毅助理教授的指導下共同參與完成的論文《一些經典算法在完全在線匹配算法的最優(yōu)分析》深入研究完全在線匹配算法并且給出了經典算法的最優(yōu)分析。二分圖在線匹配問題是由Karp et al. 首次提出，研究的是如何在在線的情況下得到盡可能大的匹配。同時提出的Ranking算法可達到最優(yōu)的近似比1-1/e。Huang et al. 首次將其拓展到了一般圖上的完全在線匹配問題，證明了Ranking算法在此模型下仍可達到高于0.5的近似。這篇文章進一步研究了完全在線匹配問題并且給出了Ranking以及Water-filling這兩個經典在線匹配算法的最優(yōu)近似比分析。同時，這篇文章的結果也改進了關于其他一些匹配模型，比如邊到達模型下的最優(yōu)下界。
由我院段然助理教授（計科50班主任）指導，2013級博士生何昊青及2016級博士生張?zhí)煲砉餐瓿傻恼撐摹哆吶旧珕栴}的動態(tài)近似算法》著眼于邊染色問題。邊染色問題是指，在一個簡單無向圖中，用盡量少的顏色對所有邊進行染色，使得相鄰的邊顏色不同。在增刪一條邊的情形下，之前最好的邊染色動態(tài)近似算法[BCHN18]，可以在O(logΔ)時間維護一個使用2Δ-1種顏色的邊染色方案，這里Δ代表圖中邊的最大度數。該論文提出一種邊染色動態(tài)近似算法，在增刪一條邊的情形下，可以在poly(log n)時間維護一個使用(1+ε)Δ種顏色的染色方案，其中ε為常數。
?SODA?由?ACM（美國計算機協(xié)會）和?SIAM（美國工業(yè)與應用數學學會）兩大國際學術組織聯(lián)合主辦，與?STOC、FOCS?一起被公認為是算法領域的三大頂級學術會議。
（文/謝琴）
版權與免責聲明：本網頁的內容由收集互聯(lián)網上公開發(fā)布的信息整理獲得。目的在于傳遞信息及分享，并不意味著贊同其觀點或證實其真實性，也不構成其他建議。僅提供交流平臺，不為其版權負責。如涉及侵權，請聯(lián)系我們及時修改或刪除。郵箱：sales@allpeptide.com