培养从事理论计算机科学研究的人才，是我国计算机科学技术事业长盛不衰的关键。随着我国从事理论计算机科学研究队伍的壮大和理论计算机科学研究水平的提高，举办理论计算机科学优秀博士生论坛，提供理论计算机科学研究的交流平台，有助于促进我国计算机科学技术事业的进步，推动理论计算机科学研究迈上新的台阶。全国理论计算机科学优秀博士生论坛，以在读博士生报告在研的理论计算机科学研究成果为主，是国内理论计算机科学的主要学术平台之一，受到我国广大计算机科学从业者和前辈的支持和帮助。该论坛首届于2020年由中科院计算所和南京大学联合承办，2021年在四川成都由电子科技大学承办。

2022年第三届理论计算机科学优秀博士生论坛拟由山东大学承办，计划2022年9月24日至9月25日在山东省青岛市举行。本次会议将邀请国内外理论计算机科学领域的著名学者组成专家咨询组，并在论坛活动期间举行博士生与专家咨询组成员参与的讨论会。

CCF TCS2022论坛 通知.pdf

贝小辉  华为理论计算机实验室首席研究员

个人简介：2012年博士毕业于清华大学，后曾在新加坡南洋理工大学与德国马克思普朗克研究所进行博士后研究。现为南洋理工大学数学系（终身）副教授，华为理论计算机实验室首席研究员。他的主要研究方向为理论计算机和计算经济学。他曾获微软奖学金，南洋助理教授奖，并指导学生获AAAI-2020最佳学生论文奖。

尹强  上海交通大学助教教授

个人简介：上海交通大学计算机系的助理教授(长聘教授)，主要研究方向为数据库系统与理论。近五年来在数据库领域的国际学术会议和期刊上发表了12篇高质量的学术论文，其中CCF A类论文10篇。尹强博士2016年于上海交通大学获得博士学位，博士求学期间的研究方向为形式化验证，他发表于ICALP 2014和 ICALP 2020 的工作解决了形式化验证方向的两个公开问题。在正式入职上海交通大学前，尹强博士先后在北京航空航天大学和阿里达摩院工作过。

左淞  Google Staff Research Scientist

个人简介：Song Zuo is a Staff Research Scientist at Google. His primary research interests are in the area of auction and dynamic mechanism design for internet advertising and general real-world applications. Song is a graduate of the Yao Class in the Institute for Interdisciplinary Information Sciences, Tsinghua University, and received his Ph.D. from the same institute in 2018.

单小涵  启元实验室研究员

个人简介：启元实验室研究员，2018年于中科院计算所获博士学位，2018-2021年于清华大学计算机系从事博士后研究工作，2021年2月加入启元实验室。主要研究方向包括组合优化、强化学习、社交网络、合作博弈等，在IANDC、 TCS、 JOCO、SAGT等领域顶级及主流期刊和会议发表论文多篇。

刘明谋  哥本哈根大学BARC实验室博士后

个人简介：哥本哈根大学计算机系BARC研究中心博士后。曾于南洋理工大学数学系担任博士后研究员。博士毕业于南京大学计算机系，师从尹一通教授。研究方向为数据结构的算法与计算复杂度。研究成果发表于 STOC、ICALP、PODS、SPAA、TOPC等期刊和会议。

邱国良 上海交通大学

个人简介：I am a third-year Ph.D. student at Shanghai Jiao Tong university under the supervision of Prof. Chihao Zhang. I am interested in theoretical computer science in general. Currently, I focus on understanding the approximability of the counting problems.

报告题目：A Perfect Sampler for Hypergraph Independent Sets

摘要：We revisit the problem of uniformly sampling independent sets in hypergraphs. We design an efficient perfect sampler for the problem under a condition similar to the asymmetric Lovász Local Lemma. When applied to d-regular k-uniform hypergraphs on n vertices, our sampler terminates in expected O(nlogn) time provided d＜c*2^{k/2}/k for some constant c＞0. If in addition the hypergraph is linear, the condition can be weaken to d＜c*2^{k}/(k^2) for some constant c＞0, matching the rapid mixing condition for Glauber dynamics. This is a joint work with Yanheng Wang and Chihao Zhang.

胡群 上海财经大学

个人简介：Qun Hu is a Ph.D student in Shanghai University of Finance and Economics, advised by professor Pinyan Lu and Hu Fu. Her research lies in the intersection of theoretical computer science and economics.

报告题目：Stability of Decentralized Queueing Network ——Beyond Complete Bipartite Cases

摘要：An important topic in algorithmic game theory is the study of the performance of systems operated by decentralized, self-interested agents, in comparison with systems under centralized control.  One such system modeling queueing systems was proposed by Gaitonde and Tardos (EC 20, 21), who studied the stability of the system when there is a centralized authority, when queues use no regret strategies, and when queues strategize ``patiently'', respectively.  Unlike games studied in the classical Price of Anarchy literature, in these queueing systems the strategy and outcome of one round impact the utility of future rounds.

In this talk, we generalize Gaitonde and Tardos's model from complete bipartite graphs to general bipartite graphs and DAGs.  In general bipartite graphs, we obtain performance analysis comparable to that by Gaitonde and Tardos, although ours reveals a connection to the dual constraints in the centralized stability conditions, and suggest that stability conditions in incomplete bipartite graphs are generally easier to satisfy.  For DAGs, we show that a straightforward generalization of the utility function considered by Gaitonde and Tardos may lead to infinite gaps between centralized and decentralized systems when the queues use no regret strategies.  We provide both a novel utility for queues and a service priority rule, which we show restore the stability conditions when queues use no regret strategies.  Lastly, for incomplete bipartite graphs, we obtain stability conditions when queues strategize patiently, giving a bound slightly worse than that of Gaitonde and Tarods [EC21] for complete bipartite graphs.

许晨阳 浙江大学

个人简介：浙江大学博士生，研究方向为运筹优化与理论计算机科学。主要是对计算机科学中一些经典问题，或是实践中优化问题的抽象建模，进行算法设计与分析。近期的研究方向集中于机器学习预测下（在线）决策优化与机制设计。

报告题目：Mechanism Design with Predictions

摘要：借助非完美的预测来设计在线算法是近年来算法设计领域热门的研究课题之一。这类算法会利用一些对在线（未知）信息的预测，在预测准确的情况下，算法的竞争比会优于传统的在线算法；而当预测完全不准时，算法的竞争比依然能得到保障，不会较传统算法下降太多。机制设计与在线算法设计存在一些相似性，两者都需要在信息不完备的条件下进行决策，那么在机制设计中，我们是否也能通过非完美的预测来给出类似特性的机制，是我们工作中考虑的关键问题。在报告里，我们将以几个经典的博弈场景引，介绍如何设计基于非完美预测的truthful机制。

高巾捷 复旦大学

个人简介： 复旦大学计算机科学技术学院博士研究生 ，主要研究方向为布尔函数、对称密码。

报告题目：On the covering radius of binary Reed-Muller codes

摘要：对称密码学作为现代密码学的一个重要分支，在实践中应用广泛。对称密码体质在硬件与软件实现上速度更快，在需要传输大量数据时通常会考虑采用对称加密，其中流密码算法的设计与应用一直是相关研究热点。在一类基于线性反馈移位寄存器的流密码体制中，布尔函数扮演着重要作用，因此使用具有良好密码学性质的布尔函数是至关重要的。本次汇报将浅谈布尔函数的相关密码学性质研究，以及在密码学的相关应用。

王盛铧 香港理工大学

个人简介： 香港理工大学计算学系在读博士生，研究方向为图论与组合优化。目前主要工作是关于t完美图和自补图等若干问题。

报告题目： On t-perfect graphs

摘要：Inspired by applications of perfect graphs in combinatorial optimization, Chvátal defined t-perfect graphs in 1970s, by a similar polyhedral characterization for perfect graphs. The long efforts of char- acterizing t-perfect graphs started immediately, but there are only partial results. We report two recent results on t-perfect graphs. We first give a full characterization of t-perfection with respect to complementation. Then we characterize fork-free t-perfect graphs and show that they are 3-colorable and can be recognized in polynomial time.

刘莹 中国科学院大学，中国科学院软件研究所

个人简介：Ying Liu is a PhD student from Institute of Software Chinese Academy of Sciences, under the supervision of Professor Mingji Xia. Her PhD thesis focuses on the complexity of counting problems, mainly about the exponential-time dichotomies of counting Constraint Satisfaction Problems and Holant problems, under counting Exponential Time Hypothesis.

报告题目： The Exponential Time Complexity of Boolean counting Constraint Satisfaction problem

摘要：As an analogue of NP, #P is the set of counting problems which can be computed by nondeterministic polynomial time Turing machines with outputting the number of accepting computations. The definition of #P-hard is also similar to NP-hard. A general counting problem is counting Constraint Satisfaction Problems (#CSP), which is parameterized by a set of local constraint functions F. Given a collection of constraints (must belong to F) defined on a set of variables, the solution to #CSP(F) is the number of assignments of variables such that all constraints are satisfied. An important aspect is the classification of #CSP, according to whether the problem can be computed in polynomial time or be #P-hard.

The counting Exponential Time Hypothesis (#ETH) states that counting Boolean Satisfiability (#SAT) cannot be computed in sub-exponential time, and drives a new direction about complexity classification of counting problems.

In this talk, we introduce a fine-grained dichotomy of complex weighted Boolean #CSP. We present the tractable conditions of the function set F when #CSP(F) can be computed in polynomial time, otherwise we can prove that it has no sub-exponential time algorithm if #ETH holds. We also introduce some universal reduction methods in the process of obtaining such a dichotomy.

陈小羽 南京大学

个人简介：南京大学计算机科学与技术系博士生，导师是尹一通教授。研究方向是理论计算机科学，主要为MCMC采样理论，近期的研究成果发表和录用于理论计算机会议FOCS 2021和FOCS 2022。

报告题目：Field Dynamics: A New Algorithmic Tool for Fast Gibbs Sampling without Degree Restriction

摘要：Field dynamics is a new algorithmic tool for sampling from the two-spin systems. We found it during the investigation of the mixing time of Glauber dynamics on two-spin systems in the critical regime. Analyzing the mixing time in the critical regime is a well-known challenging task. Previous results often need special requirements on the underlying graph (such as bounded maximum degree, triangle-free with girth lower bound, etc) forming a gap between what is generally believed. We close this gap using the field dynamics. In particular, for the general graph and within the uniqueness regime, we prove an optimal spectral gap for the Glauber dynamics on anti-ferromagnetic two-spin systems and an optimal mixing time for the Glauber dynamics on strictly anti-ferromagnetic two-spin systems.

Field dynamics even appears to be powerful for general distribution in the Boolean domain. As a demonstration, we give a near-linear time approximate sampler for the ferromagnetic Ising model with the one-sided external field by applying field dynamics to the random cluster representation of the Ising model.

曹良林 海军工程大学

个人简介：本人2004年7月本科毕业于湖南师范大学计算机科学与技术专业，2008年12月获得华中科技大学计算机科学硕士学位，2019年3月入学海军工程大学攻读通信与信息系统专业博士学位。自2004年7月至今入职九江学院担任教师。

报告题目：Research on Key Technologies of Software Defect Prediction Based on Swarm Intelligence Algorithm

摘要：在软件产品的开发过程中，软件缺陷的发现与修复是最昂贵的软件活动。为提高软件测试的成本效益，软件缺陷预测技术（Software Defect Prediction, SDP）用来自动识别含有潜在缺陷的软件模块，指导工程师分配有限的资源从事相关的软件活动。在以数据质量、度量方法、分类器性能及时间成本为约束条件下的软件缺陷预测中，基于搜索的软件工程与预测建模技术（Search-Based software engineering and Predictive Modeling, SBPM）能在约束条件竞争下寻求最优或接近最优的预测方案，受到学者一致认可。然而，在现有的SBPM技术应用中存在亟需解决的问题：（1）采用基于SBPM技术的软件缺陷预测方法应对SDP中样本不足、类不平衡及维度灾难问题时，缺乏对搜索技术性能的实际需求分析。因此，探索搜索技术的全局最优搜索能力、大规模变量优化能力、收敛性及计算复杂度等性能与应用SBPM技术的需求关系，有利于提高应用SBPM技术的灵活性。（2）缺乏有效应对SBPM技术中目标函数的频繁计算而导致高昂时间成本的预测方法。因此，探索降低时间成本的方法，有利于提高应用SBPM技术的经济效益。（3）现有的基于SBPM技术的预测方法中，缺乏有效应对同时存在多种数据质量问题的方法。本课题研究以FA为例开展基于SBPM技术的软件缺陷预测方法的研究。

周建荣 华中科技大学

个人简介：我对经典NP-hard问题和相关搜索算法的设计和优化有兴趣，研究过的问题有：最大团、最大公共子图、SAT/MAXSAT、圆装箱、集合覆盖等。同时在进行强化学习、图神经网络与NP-hard问题结合的相关研究工作。

报告题目：A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem

摘要：We propose a new and strengthened Branch-and-Bound (BnB) algorithm for the maximum common (connected) induced subgraph problem based on two new operators, Long-Short Memory (LSM) and Leaf vertex Union Match (LUM). Given two graphs for which we search for the maximum common (connected) induced subgraph, the first operator of LSM maintains a score for the branching node using the short-term reward of each vertex of the first graph and the long-term reward of each vertex pair of the two graphs. In this way, the BnB process learns to reduce the search tree size significantly and boost the algorithm performance. The second operator of LUM further improves the performance by simultaneously matching the leaf vertices connected to the current matched vertices, and allows the algorithm to match multiple vertex pairs without affecting the solution optimality. We incorporate the two operators into the state-of-the-art BnB algorithm McSplit, and denote the resulting algorithm as McSplit+LL. Experiments show that McSplit+LL outperforms McSplit+RL, a more recent variant of McSplit using reinforcement learning that is superior than McSplit.

陈昱蓉 北京大学

个人简介：Yurong Chen is a third-year PhD student from school of computer science, Peking University, advised by Prof. Xiaotie Deng. Prior to that, she obtained her bachelor degree in mathematics from Hua Luogeng Class, Shenyuan Honors of College, Beihang University. She is interested in problems at the interface of computer science and economics.  Currently, she focuses on players' strategic behaviors due to information asymmetry, with reflection on the non-realistic assumptions of classic game theory.

报告题目： Learning to Manipulate a Commitment Optimizer

摘要：Recent work showed that in a Stackelberg game the follower can manipulate the leader by deviating from their true best-response behavior. Such manipulation is computationally tractable and may result in a significant loss of utility for the leader, sometimes completely defeating the leader's first-mover advantage. A warning to commitment optimizers, the risk these findings indicate appears to be alleviated to some extent by a strict information advantage used by the manipulation. That is, the follower has full information about both players' payoffs whereas the leader does not. In this paper, we study the manipulation problem with this information asymmetry removed. The follower is not given any payoff information of the leader to begin with but has to learn to manipulate by interacting with the leader, gathering necessary information by querying the leader's optimal commitments against contrived best-response behaviors. Our results show that information asymmetry is in fact not indispensable to the follower's manipulation: the follower can learn the optimal way to manipulate in polynomial time, using polynomially many queries to the leader's optimal commitment.

刘强 国防科技大学

个人简介：国防科技大学计算机学院2021级博士生，师从蔡志平教授。攻读博士学位期间，发表和在投CCF-A类国际会议3篇（ACM MM、CCS、AAAI），主持湖南省研究生科研创新项目1项。主要研究方向包括：深度学习、AI安全、图像隐写等。

报告题目：Opportunistic Backdoor Attacks: Exploring Human-imperceptible Vulnerabilities on Speech Recognition Systems

摘要：基于大规模音频数据训练和更新的语音识别系统很容易受到在系统训练中注入专用触发器的后门攻击。使用的触发器通常是人类听不到的声音，比如超声波。然而，我们注意到这样的设计是不可行的，因为它可以很容易地通过预处理被过滤掉。在这项工作中，我们首次提出了语音识别的可听后门攻击范式，其特点是被动触发和机会调用。传统设备合成的触发器被日常场景中的环境噪声所取代。为了使触发器适应语音交互的应用动态，我们利用从上下文中继承的观察知识来训练模型，并提出基于确定性的触发器选择、性能无关的样本绑定和触发器延迟增强技术来适应注入和中毒。大量的实验在理想的实验室环境和现场环境(模拟)下进行，实验结果验证了所提方法的有效性、鲁棒性、以及在有无防御时攻击模型的可行性。我们相信识别这种新型的漏洞可以促进语音识别系统的安全发展。

杨帅 中国科学院计算技术研究所

个人简介：Shuai Yang is a fifth-year PhD student from Insititute of Computing Technology, Chinese Academy of Sciences, advised by Prof. Jialin Zhang. Prior to that, he obtained his bachelor degree in computer science from Sichuan University. He is interested in problems at the quantum computation.  Currently, he focuses on the quantum circuit synthesis and quantum circuit optimization.

报告题目：Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis

摘要：The Quantum State Preparation problem aims to prepare an n-qubit quantum state |ψv>=∑k vk|k> from the initial state |0>n, for a given unit complex vector v with |v|2=1. The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth complexity remains open when ancillary qubits are available. In this paper, we study quantum circuits when there are m ancillary qubits available. We construct, for any m, circuits that can prepare |ψv> in depth O(2^n/(m+n) + n) and size O(2^n), achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of Θ(4^n/(m+n)) for quantum circuits implementing a general n-qubit unitary for any m≤O(2^n/n) number of ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits. And for circuits with sufficiently many ancillary qubits, our result quadratically improves the currently best upper bound of O(4^n) to Θ(n2^n).

Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide parameter regime. The results can be viewed as (optimal) time-space tradeoff bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.

赵景阳 电子科技大学

个人简介：电子科技大学计算机学院2021级博士研究生，师从肖鸣宇教授。主要从事组合优化、调度、网络保护、图算法等方向研究。目前在AAAI、IJCAI、MFCS、COCCON等会议上发表4篇论文。

报告题目：Approximation Algorithms for the Traveling Tournament Problem

摘要：在体育类调度问题中，旅行锦标赛问题（Traveling Tournament Problem）是一个经典的组合优化问题。在该问题中，我们需要设计一个双循环赛使得所有队伍的旅行距离之和最小，其中双循环赛要满足以下三个条件：每个队伍都与其他每个队伍打两场比赛（一场主场比赛，一场客场比赛）；每个队伍最多能打k场连续的客场/主场比赛；每对队伍不能在连续两天内碰面。本报告将介绍该问题的近似算法最新研究成果。

李甜甜 山东大学

个人简介：山东大学在读博士生，本科毕业于山东大学数学学院，现于山东大学计算机科学与技术学院攻读博士学位。目前主要研究领域为计算生物方面的基因组序列的重组、分析、比较相关问题，包括参数算法及近似算法设计、计算复杂性证明

报告题目：Sorting Strings by Flanked Block-Interchanges

摘要：Rearrangement sorting problems aim to measure genome similarities and play a crucial role in string comparisons. A challenging evidence against classical rearrangement sorting problems was verified many times in genome data analysis and discloses that, repeated ends are associated with rearrangement involved segments and stay unchanged before and after rearrangements.

To reflect this evidence, we consider a novel rearrangement operator that exchanges among a string two sub-strings flanked with identical left as well as right symbols. This operator guarantees for breakpoints to stay the same before and after it performs on a string and will be called a flanked block-interchange. The problem of sorting strings by flanked block-interchanges is formulated as finding a shortest sequence of flanked block-interchanges to transform a string into the other.

We first present a linear time algorithm to decide whether there is a sequence of flanked block-interchanges to transform a string into the other. We then present a quadratic time algorithm for finding a shortest sequence of flanked block-interchanges to transform one string into the other where in a given string each symbol occurs at most twice. In addition, we present a quadratic time algorithm to find a sequence of at most O(k) times the minimum number of flanked block-interchanges to transform a string into the other if in a given string each symbol occurs at most k times. The performance ratios of our algorithm are 2.2075 and 8 for k = 3 and 4. We show that sorting strings by flanked block-interchanges is NP-Hard at last.

王思为 国防科技大学

个人简介：国防科技大学博士三年级学生，导师为祝恩和刘新旺教授，主要研究方向是无监督多视图学习、大规模图学习和深度异常检测。研究成果在CVPR/ICML/ICCV/IJCAI/AAAI/TIP/TKDE/TNNLS/TMM等会议期刊上发表，担任ICLR/AAAI/IJCAI/ACM MM/CVPR/ICCV/ECCV/NIPS的审稿人、SPC/AC，其个人主页在https://wangsiwei2010.github.io/。

报告题目：Report on Large-scale Multi-view Clustering Study

摘要：当前，多视图数据广泛地出现在机器学习、数据挖掘领域。然而，最近大量研究表明现有多视图方法仍存在一些急需解决的问题：1.设计高效的大规模多视图算法来应对大规模挑战；2.设计有效的面对缺失信息的多视图算法来应对信息不完全挑战；3.理解大规模多视图融合的理论依据。本报告拟介绍报告人最近几年在大规模多视图的探索，阐述完整、缺失条件下基于二部图的大规模工作。

张双俊 复旦大学

个人简介：本科毕业于北京理工大学，2017年至今在复旦大学计算机学院攻读网络空间安全博士学位。其主要的研究方向为零知识证明与计算复杂性，以第一作者在TCS期刊上发表文章一篇。

报告题目：Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs

摘要：Succinct Non-Interactive Arguments (SNARGs) [1], also known as verifiable computing protocols, are cryptograhy proofs for delegation of computation. Such proof systems enable the prover to provide a very short certificate π to ensure the correctness of the long computation and the verifier can verify the validity of π quickly.

We design a new preprocessing succinct non-interactive argument (SNARG) for rank-1 constraint satisfiability (R1CS) from holographic Interactive Oracle Proofs (IOPs). The protocol is secure in the random oracle model (ROM). We achieve polylogarithm time verifier and polylogarithm proof size. Our construction consists of two parts: (1) a holographic IOP for R1CS with linear size proof and logarithmic query complexity. (2) A cryptography complier converts holographic IOPs to SNARGs. In the first part, univariate sumcheck and low degree testing play an important role in the holographic IOP. In the second part, we use Merkle tree scheme and Fiat-Shamir heuristic to achieve succinctness and non-interactivity.

王力冠 复旦大学

个人简介：在读博士生。研究兴趣：密码学，零知识证明。

报告题目：A New Construction of Simulation-Extractable SNARKs

摘要：Working after Groth’s pairing-based zkSNARK, we construct a simulation extractable zkSNARK under the random oracle model. We point out that the random oracle model can be removed, assuming the existence of linearly collision-resistant hash functions, which arises naturally and is satisfied by a random oracle. We also extend our result to simualtion extractable and subversion zero-knowledge SNARKs for QAP. Overall, our construction compares well with the state-of-art SE-zkSNARKs.

周建奇 山东大学

个人简介：山东大学计算机科学与技术学院在读博士生，论文“Parameterized Approximation Algorithms for TSP”已被ISAAC 2022（The 33rd International Symposium on Algorithms and Computation）会议接收。

报告题目：Parameterized Approximation Algorithms for TSP

摘要：我们研究一般图上的旅行商问题the Traveling Salesman problem (TSP)。在旅行商问题中，给定n个顶点的完全无向图G=(V,E)和边的权值函数c: E→R_{>=0},目标是寻找一个权值总和最小的访问每个顶点仅一次的回路。众所周知，除非P = NP，对于任意可计算函数ρ，TSP不存在多项式时间的ρ(n)近似。而在度量空间下（即边的权值函数满足三角不等式），TSP存在多项式时间的1.5近似。

我们从参数近似算法的角度研究一般图上的TSP问题。一个近似比为ρ的参数近似算法在f(k) |I|^{O(1)}时间内返回一个近似比为ρ的解，在这里f是一个可计算函数，k是输入实例I的一个参数。我们引入了两个参数来度量给定的TSP实例和度量空间下TSP实例的差异，并得出下面两个结果：

（1）一个在O((3k_1)! 8^{k_1} n^3)时间内近似比为3的TSP参数近似算法，这里k_1是边权值违反三角不等式的三角形个数。

（2）一个在O(n^{O(k_2)})时间内近似比为3的TSP近似算法和一个在O(k_2^{O(k_2)} n^3)时间内近似比为6k_2+9的TSP参数近似算法，这里k_2是最小的顶点集合大小使得删除该集合中的所有点后边权值都满足三角不等式。

据我们所知，上述算法是在一般图上第一次给出的非平凡的TSP参数近似算法。

张烜 山东大学

个人简介：山东大学计算机科学与技术学院博士在读，主要研究方向及兴趣为小分子性质预测、蛋白质结构预测等。目前在BIBM会议中一篇论文在投，另外有三篇合作论文。

报告题目：CoAtGIN: Marrying Convolution and Attention for Graph-based Molecule Property Prediction

摘要：Molecule property prediction based on computational strategy plays a key role in the process of drug discovery and design, such as DFT. Yet, these traditional methods are time-consuming and labour-intensive, which can’t satisfy the need of biomedicine. Thanks to the development of deep learning, there are many variants of Graph Neural Networks (GNN) for molecule representation learning. However, whether the existed wellperform graph-based methods have a number of parameters, or the light models can’t achieve good grades on various tasks. In order to manage the trade-off between efficiency and performance, we propose a novel model architecture, CoAtGIN, using both Convolution and Attention. On the local level, k hop convolution is designed to capture long-range neighbour information. On the global level, besides using the virtual node to pass identical messages, we utilize linear attention to aggregate global graph representation according to the importance of each node and edge. In the recent OGB Large-Scale Benchmark, CoAtGIN achieves the 0.0933 Mean Absolute Error (MAE) on the large-scale dataset PCQM4Mv2 with only 5.6 M model parameters. Moreover, using the linear attention block improves the performance, which helps to capture the global representation.

仝心 山东大学

个人简介：山东大学计算机科学与技术学院在读博士生，导师为姜海涛教授，研究方向为算法和计算复杂性。

报告题目：Decision Algorithms and Complexity for Sorting by Symmetric Reversals

摘要：Sorting a permutation by reversals is a famous problem in genome rearrangements, and has been well studied over the past thirty years. But the involvement of repeated segments is inevitable during genome evolution, especially in reversal events. Since 1997, evidence was found that in many genomes the reversed regions are usually flanked by a pair of inverted repeats. For example, a reversal will transform +a + x - y - z - a into +a + z + y - x - a, where +a and -a form a pair of inverted repeats. This type of reversals are called symmetric reversals, which, unfortunately, were largely ignored until recently. In this paper, we investigate the problem of sorting by symmetric reversals, which requires a series of symmetric reversals to transform one chromosome into the other. We present an O(n²) time algorithm to determine whether a chromosome can be transformed into the other by a series of symmetric reversals. (The decision problem of sorting by symmetric reversals is referred to as SSR.) We also study the optimization version (referred to as SMSR) that uses a minimum number of symmetric reversals to transform one chromosome into the other. We design an O(n²) algorithm for a special 2-balanced case of SMSR, where chromosomes have duplication number 2 and every repeat appears twice in different orientations. We finally show that the general case of SMSR is NP-hard.

论坛主席

孙晓明（中科院计算所）

成秀珍（山东大学）

论坛程序委员会
孙晓明（中科院计算所）
蔡志平（国防科技大学）
尹一通（南京大学）
张家琳（中科院计算所）
肖鸣宇（电子科技大学）

论坛当地组织委员会

朱大铭（山东大学）

郭炅（山东大学）

冯好娣（山东大学）

崔学峰（山东大学）

姜海涛（山东大学）

时阳光（山东大学）

崔婧华 山东大学：tcs202209@163.com

陈成（学生负责人）：nihaojingyou@163.com