算法與邏輯團隊的Bakh Khoussainov教授為通信作者的論文 Defining algorithmically presented structures in first order logic 被計算機理論方向的國際頂級會議LICS 2024接收。LICS全名為ACM/IEEE Symposium on Logic in Computer Science,是理論計算機科學中邏輯方向最頂級的會議,2024年全球283篇投稿中僅接收了72篇(接收率為25%),其中來自中國作者的論文僅此一篇。
此文主要研究是否可以使用一階邏輯來正式描述算法表示的結構。這一問題的研究可追溯到50~60年前的古老經典問題,該領域的許多著名專家均嘗試過解決這個問題,但是始終沒有得到很好的解決方案。Bakh Khoussainov教授潛心在該問題上研究了20余年,最終提出了解決這一問題的積極方法。
算法與邏輯團隊的Toru Takisaka教授為第一作者、碩士生王長江為第三作者的論文 Lexicographic Ranking Supermartingales with Lazy Lower Bounds 被計算機理論方向的頂級國際會議CAV 2024接收。CAV全名為International Conference on Computer Aided Verification,是形式化認證中最頂級的國際會議之一,該會議關注從理論到具體應用的各方面研究成果,特別是實用的驗證工具以及實現它們所需的算法和技術。
這篇論文主要研究的是Ranking Supermartingale(簡稱RSM)技術,它是一種用于自動驗證概率程序幾乎必定終止的重要技術。在該論文中,作者提出了第一種系統分析弱非負性條件下RSM穩健性的技術,基于這一技術,該文設計了一個新的RSM變體,其非負性條件明顯弱于現有技術中最先進的RSM變體。實驗表明,該項新型RSM合成算法相對現有最先進算法,可行性提高了10.4%。
除以上兩篇論文之外,算法與邏輯團隊還有四篇論文同時被CCF A類會議IJCAI 2024中的規劃、優化、約束滿足等傳統人工智能基礎算法領域接收。IJCAI全名為International Joint Conference on Artificial Intelligence,是人工智能領域歷史最長、知名度最高的會議之一,其中傳統人工智能基礎和理論方向是該會議中難度最大、競爭最激烈的方向之一。四篇被接收的論文具體信息如下:
論文 A Fast Algorithm for MaxSAT Above Half Number of Clauses ,第一作者為博士生彭俊強,第二作者為導師肖鳴宇教授。該文研究了最大可滿足性問題(Maximum Satisfiability Problem)以“輸入公式的最大可滿足子句數與一半子句數之差”這一度量為參數的算法,給出當前最佳的運行時間上界。
論文 A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling ,第一作者為博士生趙景陽,第二作者為導師肖鳴宇教授。該文研究了二分旅行錦標賽問題(Bipartite Traveling Tournament Problem)的調度算法,給出的算法達到了當前最好的理論近似率。
論文 Improved Approximation Algorithms for Capacitated Location Routing ,第一作者為博士生趙景陽,第二作者為導師肖鳴宇教授,第三作者為碩士生汪順旺。該文研究帶容量限制的選址路徑規劃問題(Capacitated Location Routing),給出的算法改進了原有最佳近似算法。
論文 Exactly Solving Minimum Dominating Set and its Generalization ,第一作者為碩士生熊子良,第二作者為導師肖鳴宇教授。該文針對最小支配集問題及其擴展問題設計了快速的算法,給出了新的約簡規則、新的理論下界等,實驗效果顯示新的算法比原有最佳算法能快上10^5倍。
電子科技大學算法與邏輯團隊由歐洲科學院院士、新西蘭院士Bakh Khoussainov教授和算法專家肖鳴宇教授共同組建,許超教授、Toru Takisaka教授、周毅副教授、郝東副教授等多位老師參與。該團隊致力于基礎理論研究,以探索算法難題和解決重要的科學問題為宗旨,激發和培養學生及青年老師對算法和基礎理論的興趣,為算法及相關研究方向感興趣的師生提供一個交流平臺。團隊目前重點關注的研究方向包括:算法設計與分析(包括近似算法、參數算法、精確算法、在線算法等),邏輯、圖論與圖算法,組合優化,算法工程,機制設計與算法博弈論,形式化方法與認證等。團隊培養的學生人均發表一篇CCF A類論文,多名學生在程序設計競賽和數學競賽中取得優異成績,如:在ACM程序設計競賽中10余人進入世界總決賽;在IEEE極限編程競賽中連續兩次獲得世界第二名,六次進入世界前十名;兩次獲得華為軟件精英挑戰賽全球總決賽冠軍;2023年獲得全國大學生數學競賽(非數學類)全國第一名等。