2023年济南算法与计算理论学术研讨会

一、会议简介

算法与计算理论是理论计算机科学的主要研究领域之一，是软件学科的基础研究内容。本次会议邀请了国内算法和计算领域的著名学者，就最新优秀研究成果做学术报告，欢迎广大师生参加。

二、 会议基本情况

        1. 主办单位（邀请人）：山东大学软件学院，张鹏。

        2. 会议时间：2023年11月29日下午。

三、 会议日程

四、 专家报告

        1.报告专家：栗师

报告题目：Title: Improved approximation algorithms for correlation clustering using pre-clustering and cluster LP

摘要：We consider the classic correlation clustering problem: Given a complete graph where edges are labelled either + or -, the goal is to find a partition of the vertices that minimizes the number of the +edges across parts plus the number of the -edges within parts.  Recently, Cohen-Addad, Lee and Newman presented a 1.994-approximation algorithm for the problem using the Sherali-Adams hierarchy, hence breaking through the integrality gap of 2 for the classic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev. We present several techniques that improve the state-of-the-art approximation ratio. We propose the cluster LP as a strong linear program that might tightly capture the approximability of Correlation Clustering. It unifies all the previous relaxations for the problem. It is exponential-sized, but we show that it can be (1 + ε)-approximately solved in polynomial time for any ε > 0, using a preclustering technique we introduced. It allows us to essentially ignore the error arising from the correlated rounding used by Cohen-Addad et al. We demonstrate the power of the cluster LP by presenting a simple rounding algorithm, and providing two analyses, one analytically proving a 1.49-approximation and the other solving a factor-revealing SDP to show a 1.437-approximation. This is based on joint work with Cohen-Addad, Lee and Newman, in FOCS 2023, and an ongoing work with Cao, Cohen-Addad, Lee, Newman and Vogl.

简介：栗师，南京大学教授、博士生导师。本科毕业于清华大学计算机科学与技术系，以及第一届姚期智理论计算机科学实验班。于普林斯顿大学获得博士学位，之后在芝加哥丰田技术研究院担任助理研究教授，纽约州立大学布法罗分校担任助理教授，并于2020年在该校获得副教授职称。2023年初入职南京大学。栗师教授的研究方向为理论计算机科学领域与算法设计。他在若干经典和基础问题上做出重大突破，解决了很多十多年未能解决的公开难题。其多个结果分别获得获得理论计算机科学一流会议ICALP 2011获单独作者最优秀学生论文奖、领域顶级会议FOCS 2012最优秀论文奖和发表于计算机科学领域的旗舰期刊 Journal of the ACM (JACM)上。多项结果发表在理论计算机科学最高期刊SIAM Journal on Computing (SICOMP) 上，以及ACM Transactions on Algorithms (TALG)，Information and Computation(I&C)等国际一流期刊上。他在FOCS, STOC和SODA三大领域顶级会议上发表文章30余篇。

2.报告专家：刘景铖

报告题目：Optimal Bounds on Private Graph Approximation

摘要：We propose an efficient epsilon-differentially private algorithm, that given a simple weighted n-vertex, m-edge graph G with a maximum unweighted degree Delta, outputs a synthetic graph which approximates the spectrum within O(min{Delta(G), sqrt{n}) on the purely additive error. To the best of our knowledge, this is the first epsilon-differentially private algorithm with a non-trivial additive error for approximating the spectrum of the graph. One of the subroutines of our algorithm also precisely simulates the exponential mechanism over a non-convex set, which could be of independent interest given the recent interest in sampling from a log-concave distribution defined over a convex set. Spectral approximation also allows us to approximate all possible (S, T)-cuts, but it incurs an error that depends on the maximum degree Delta(G). We further show that using our sampler, we can also output a synthetic graph that approximates the sizes of all (S, T)-cuts on n vertices weighted graph G with m edges while preserving (epsilon, delta)-differential privacy and optimal additive error for weighted graphs. This removes the gap in the upper and lower bound in Eliáš, Kapralov, Kulkarni, and Lee (SODA 2020). Based on joint work with Jalaj Upadhyay and Zongrui Zou.

简介：刘景铖，南京大学副教授，博士生导师。本科毕业于上海交通大学ACM试点班。博士毕业于加州大学伯克利分校，师从哥德尔奖得主Alistair Sinclair。毕业后在加州理工学院担任Wally Baer and Jeri Weiss讲席博士后。主要研究方向包括随机算法，计算的相变理论和理论计算机科学，入选国家青年高层次人才。代表成果全部发表在STOC, FOCS, SODA和Journal of the ACM, SIAM Journal on Computing等国际一流的会议与期刊上。曾参与起草并组织ACM STOC 2020会议的专题讨论workshop。

3. 报告专家：杨雨

报告题目：On enumerating algorithms of novel multiple leaf-distance granular regular alpha-subtrees of trees

摘要：Subtrees and BC-subtrees (subtrees in which the distance between any two leaves is even) are important concepts in the study of complex graphical structures. In this article, we propose a novel generalization called the leaf-distance granular regular alpha-tree (abbreviated as LDR alpha-tree for short). This is a tree in which the distance between any two leaves is divisible by alpha (alpha is a positive integer). An LDR alpha-subtree is simply a subtree that is also a LDR alpha-tree. We present basic properties and generating functions related to the LDR alpha-subtrees enumeration. Based on those theoretical results we provide efficient algorithms for enumerating various LDR alpha-subtrees of trees. Our algorithms can serve as multi-distance granularity sifters of a graph to screen all the α-subtree uniformly, and thus provide novel insights into exploring new structural properties from the perspective of multiple leaf-distance granularity.

简介：杨雨，博士（后），副教授，硕士研究生导师，研究方向：理论计算机、图计算。入选河南省学术技术带头人、河南省高校科技创新人才，是美国数学评论(MR)评论员，中国计算机学会高级会员，CCF理论计算机科学专委委员，TCS等7个主流SCI期刊审稿人。主持完成国家自科基金青年项目，博士后基金面上项目、省高校科技创新人才等项目多项，出版学术专著和教材2部，近年来在CCF A类期刊Information and Computation在内的主流期刊上发表高水平论文20余篇。

4. 报告专家：刘彬

报告题目：Streaming Algorithms for Maximizing Submodular Functions

摘要：Submodular functions play a key role in combinatorial optimization field. The general problem of optimizing a submodular function subject to different constraints captures lots of problems both in theory and in practice, including maximum coverage, maximum cut, facility location, social welfare maximization, influence maximization in social networks, sensor placement, etc. On the other hand, in the current big data environment, the input data of many applications is much larger than the storage capacity of individual computer. In this case we need to process data by using the streaming model. In this talk, I will show several streaming algorithms for the problem of maximizing submodular functions with different constraints.

简介：刘彬，中国海洋大学数学科学学院教授、博导、院长助理。2010年毕业于山东大学运筹学与控制论专业，获理学博士学位。2016年作为访问学者赴美国德克萨斯大学达拉斯分校访问一年。研究领域和兴趣包括：次模优化、近似算法的设计与分析、图论及其应用等。在Journal of Global Optimization、Journal of Graph Theory、Journal of Combinatorial Optimization等期刊和INFOCOM等会议发表论文50余篇，先后主持国家自然科学基金面上项目等科研项目共8项。目前担任中国工业与应用数学学会副秘书长、信息和通讯技术领域的数学专委会委员，中国运筹学会图论组合分会理事和副秘书长、数学规划分会青年理事和副秘书长，山东省运筹学会理事，美国数学会Mathematical Reviews评论员等。