TCSPhD

General Information

2020年11月21日，周六， 9 am--6 pm.

Zoom在线会议，哔哩哔哩同步直播（Zoom和直播信息稍后公布）

会议日程

会议日程
9:00 -- 9:10	孙晓明中科院计算所	开幕词
9:10 -- 9:40	张天翼清华大学	题目: Incremental single source shortest paths in sparse digraphs 摘要: Given a directed graph [math]\displaystyle{ G = (V, E, \mathbf{w}) }[/math] with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graph [math]\displaystyle{ G }[/math]. In a very recent paper, [Gutenberg et. al., 2020] proposed a deterministic algorithm for this problem with [math]\displaystyle{ \tilde{O}(n^2\log W) }[/math] total update time, where [math]\displaystyle{ n = \|V\| }[/math] and [math]\displaystyle{ W }[/math] denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions [math]\displaystyle{ m }[/math] is [math]\displaystyle{ \tilde{\Omega}(n^2) }[/math], their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzinger et. al., 2014], whose algorithm is randomized and works in [math]\displaystyle{ \tilde{O}(mn^{0.9}\log W) }[/math] total update time under the assumption of oblivious non-adaptive adversary. In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with [math]\displaystyle{ \tilde{O}(m^{5/3}\log W) }[/math] total update time. The second one is a randomized algorithm with [math]\displaystyle{ \tilde{O}((mn^{1/2} + m^{7/5})\log W) }[/math] total update time, which improves over both previous results when [math]\displaystyle{ m = O(n^{1.42}) }[/math]; moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break the [math]\displaystyle{ O(mn) }[/math] bound with adaptive adversaries for sparse graphs. Joint work with Shiri Chechik from Tel Aviv University.
9:40 -- 10:10	白宗磊北京大学	题目: The approximability of ferromagnetic 2-spin systems 摘要: Spin systems model the interactions between neighbors on graphs, An important special case is when there are only 2 spins, which encompass many important models in sampling and counting problems, including the famous Ising model, Hard-core model, etc. The approximability of 2-spin systems is widely studied in statistical physics, machine learning, probability theory, and theoretical computer science. The partition function can be viewed as polynomial on the external fields. For bounded degree graphs, I will present the zero-free region for ferromagnetic 2-spin systems, which implies an FPTAS based on the method introduced by Barvinok. On the other hand, we give #BIS-hard result for the external fields on the interval with respect to the degree bounds. The upper bound of the interval coincides with boundary of the zero-free region, which implies a complexity transition at the point.
10:10 -- 10:40	包奇复旦大学	题目: 基于拉普拉斯求解器的图数据挖掘算法摘要: 2004年，耶鲁大学教授 Daniel A. Spielman 提出了一种基于图稀疏化的求解拉普拉斯矩阵方程组的快速近似算法，并随后开发出了相关的代码库 Laplacians.jl。该算法时间复杂度低且精度高，其代码库在实际运行过程中效果良好。如何运用该求解器来有效解决图数据挖掘中遇到的问题？本报告将通过展示几个具体的案例来说明。
茶歇
10:55 -- 11:25	李斌电子科技大学	题目: 基于社交网络的拍卖机制设计理论研究摘要: 拍卖是资源分配最有效的形式。传统的拍卖机制面临着参与人数少，竞争不激烈的问题，这不仅会导致资源分配的低效性，还会限制卖家出售资源所获得的收益。在本次分享中，我们提出一套基于社交网络的拍卖机制框架。在该框架中，所有潜在的买家构成一张网络，网络中的节点只能和其邻居进行信息交换；卖家位于网络中的某个节点，并且在初始状态下，只有卖家的邻居知晓有关拍卖的信息。我们的目标是激励卖家的邻居主动分享拍卖信息给他们网络中的邻居，并由此形成级联反应，最终使得网络中所有买家知晓拍卖信息并参与进拍卖中来。这种内生的信息分享行为不仅会使得物品得到更有效的配置，也能够潜在地提高卖家的收益。我们刻画了所有满足个体理性，激励相容的传播拍卖机制；此外，我们具体分析了两类传播拍卖场景：无权网络场景和有权网络场景。针对这两类场景，我们设计了相应的传播拍卖机制，这些机制不仅能够激励信息传播，而且相比于传统拍卖，卖家的收益以及物品配置的效率上都得到了理论性的提升。
11:25 -- 11:55	王思为国防科学技术大学	题目: 基于后期融合的大规模多视图算法研究摘要: 物体的不同视图描述了物体的不同特性,如何利用这些视图的互补信息和兼容信息充分发挥各自优势,规避各自局限,是目前学术界研究的热点问题,这类信息融合的方法统称为多视图学习算法。与单视图学习算法不同,多视图学习算法能够学习到的特征更加全面,也更加鲁棒，但是现有的多视图聚类受限于样本立方的复杂度而限制了在大规模数据集上的应用。本报告基于我们所提出的基于后期融合的大规模多视图聚类算法，并提出尽可能多的现有大规模多视图算法的关键技术问题。
午餐
14：00 -- 14:30	吴步娇中科院计算所	题目: 有限辅助比特下CNOT电路的优化摘要: 由于量子计算机现阶段实现过程中的消相干问题，通过并行化量子电路来降低电路深度对量子算法的有效实现具有很大的价值。我们证明了任何n量子比特的CNOT电路在有[math]\displaystyle{ m }[/math]个辅助比特的情况下都可以优化为深度[math]\displaystyle{ O(\log n + n^2/(n+m)\log (n+m)) }[/math]。我们也证明了该算法得到的深度是渐近最优的。此外，因为当下较为流行的一种量子设备——超导量子电路的量子比特的连通性具有一定限制。因此，我们也考虑了带拓扑约束的CNOT电路的优化，并给出了相应的下界。
14：30 -- 15:00	张舒山东大学	题目: 最长公共样本子序列算法摘要: 寻找基因组中的保守基因在大豆分子育种、疫苗研发等研究中具有重要意义。为找到在不同的基因组中次序保持一致的保守基因序列，我们提出了带索引的最长公共样本子序列问题。给定两个线性基因组以及每个线性基因组的索引基因子序列，要求找到这两个线性基因组的一个最长公共样本子序列，并且该最长公共样本子序列的一个子序列和给定的索引基因子序列相同。为解决这一问题，我们提出了一个动态规划算法，此算法所需的时间和空间有随着索引基因子序列长度的增加而减少的趋势。我们在23对人/大猩猩染色体对上进行了实验，并分别找到了它们的最长公共样本子序列，这些子序列的基本单元为已经注释的基因或者伪基因，即一段连续的碱基序列。通过比较算法得到的伪基因和已经注释的基因，在人的7号和16号染色体上，我们分别找到超过1000和500个伪基因在人和大猩猩染色体对中顺序一致并且与任何已经注释的基因没有重叠，这些伪基因中很有可能存在一些新的基因或者motif。
15：00 -- 15:30	张文博上海交通大学	题目: 互模拟等价性验证问题研究摘要: 判定两个系统在语义上是否等价是验证领域的一个基本问题。互模拟等价是最受研究者们关注的等价关系之一。近年来，有不少无限状态系统上的互模拟等价问题都取得了重要突破。本次报告中，我们将会对领域内最新的研究成果和技术做一个尽可能全面的总结，并介绍我们的一些最新结论。
茶歇
15：45 -- 16:15	刘明谋南京大学	题目: 关于简洁数据结构复杂度的一些研究摘要: 数据结构是计算机科学的基石。本报告考虑了三个根本的数据结构问题的简洁数据结构。首先我们为范围最值查询问题证明复杂度下界。我们为该问题证明了首个复杂度下界，并且该下界证明了当前最好的算法在常数时间复杂度下的最优性。我们通过彻底重构前人的复杂度下界证明技术，使得我们不再只能证明平均情况的复杂度下界，而是能够证明更高的最坏情况的复杂度下界。然后我们考虑动态的近似集合成员查询问题（也被称为布隆过滤器问题）。我们考虑了一个具有很强现实意义、有趣但又很少被理论界考虑的设定：动态的数据结构可以使用动态的空间占用，但是其空间占用仅依赖于当前数据集的大小，而不是预先估计的最大大小。在这样的设定中，我们为动态的近似集合成员查询问题构造了目前为止在所有意义上的最优的数据结构：在空间上，它是唯一一个解决该问题的简洁数据结构；在时间上，它的所有更新和查询操作都可以在最坏情况的常数时间内完成。我们的数据结构为 Pagh, Segev和Wieder (FOCS 2013) 提出的开放性问题给出了一个肯定的回答。最后我们考虑另一个根本性的数据结构问题，字典问题。我们构思了一种全新的思路来处理经典的字典数据结构中会导致空间浪费的“溢出”问题。通过这样的全新策略，我们的额外空间开销从个[math]\displaystyle{ O(n(\log n)^{2/3}\log\log n) }[/math]比特降低到了个[math]\displaystyle{ O(n\log\ldots\log n) }[/math]比特，同时也保证了所有的更新操作和查询操作都可以在最坏情况的常数时间内完成。我们的数据结构为 Arbitman, Naor和Segev (FOCS 2010) 提出的开放性问题给出了一个肯定的回答。
15：15 -- 16:45	秦旭东华东师范大学	题目: 量子程序的互模拟验证摘要: 量子进程代数是基于经典的进程代数提出的，用于量子程序的形式化验证。量子进程代数有一种重要的应用，就是形式化地验证量子通信协议。其中有一种想法是，只要有合适的对行为等价性的定义以及一个判定方法，就可以判断一个协议的实现是否与该协议的规范是否是一致的，即可验证协议。本论文中考虑的量子基互模拟对量子程序来说便是一个方便使用的行为等价性定义。我们设计并实现了两个on-the-fly 算法，用于检测两个量子CCS 编写的量子程序之间的强基互模拟以及弱基互模拟。此外，我们还定义了基于分布的量子程序基互模拟，其在表现量子操作的等价性方面有更好的效果。我们同样实现了一个基于分布的量子程序基互模拟检测算法，并将其与基于状态的算法进行了比较实验。对上述算法，我们证明了算法的可终止性与正确性，并分析了算法的时间复杂度。并且基于算法的实现我们开发了一个工具QBisim，用于验证各种有名的量子协议，例如量子隐态传输协议、量子密钥分发协议、BB84 量子密钥分配方案等。我们通过工具对这些量子通信协议进行了实验，实验结果表明了工具是有效的。
16:45 -- 18:00	专题讨论：读博经历与求职经验分享会嘉宾：黄棱潇（华为TCS实验室）；李乾（深圳大学）; 刘正阳（北京理工大学）；邵帅（牛津大学）；张驰豪（上海交通大学)

报告人个人简介

	张天翼，清华大学交叉信息研究院博士五年级，导师是段然副教授，研究方向是图论算法与数据结构。
	Zonglei Bai（白宗磊） is a Ph.D student in Department of Computer Science and Technology， Peking university, and he is supervised by Professor Hanpin Wang. His research focuses on approximation algorithms for counting and sampling problems. Typical problems include computing marginal probabilities and expectations of random variables, the evaluation of partition functions, etc.
	包奇，复旦大学计算机科学技术学院博士研究生，本科毕业于复旦大学，在 TCS 和 ICDM（2019）上以第二作者的身份发表过两篇论文。
	李斌，电子科技大学2017级博士生。2015年毕业于重庆邮电大学智能科学与技术专业，获学士学位。主要研究兴趣是不完美信息下的多方最优决策（如机制设计，拍卖理论等），以及多智能体交互场景下的算法设计与实现。研究成果发表在多个传统人工智能顶级会议上，如AAAI,IJCAI，AAMAS等。
	王思为，国防科技大学计算机学院博士在读，主要研究兴趣为多视图融合、深度无监督学习和缺失信息学习等。发表论文11篇（CCF-A类论文3篇），担任人工智能领域顶级会议和期刊AAAI2019-2020、IJCAI2019-2020、CVPR、ICME、TCYB、TNNLS、TIP等审稿人。参与国家先导研究项目、科技部重大专项、自然科学基金项目等七项和部队重大工程1项。曾获国家级无人机挑战赛一等奖、国防科技大学强军奖学金。
	吴步娇，中国科学院大学计算技术研究所博士在读，导师是孙晓明研究员。主要研究方向为量子计算，量子电路优化与经典验证。曾在SODA, TPDS, Science Bulletin等国际知名会议和期刊上发表论文。
	张舒，山东大学在读博士生，本科毕业于山东大学软件学院，现于山东大学计算机科学与技术学院攻读博士学位。目前主要研究领域为计算生物方面的基因组序列的重组、分析、比较相关问题，包括参数算法及近似算法设计、计算复杂性证明。
	张文博，上海交通大学BASICS实验室在读博士生，师从傅育熙教授。本科毕业于东南大学。目前的主要研究领域为理论计算机科学，包括形式化验证，自动机理论，进程演算等。
	刘明谋，南京大学博士生，导师尹一通和姚鹏晖，主要研究兴趣为数据结构复杂度。论文发表于STOC、ICALP和SPAA，获得SPAA2016杰出论文奖。
	秦旭东，华东师范大学软件工程学院在读博士研究生，导师是华东师范大学软件工程学院邓玉欣教授。目前的研究方向为形式化方法，主要的内容为量子程序的形式化验证。

会议日程
9:00 -- 9:10	孙晓明中科院计算所	开幕词
9:10 -- 9:40	张天翼清华大学	题目: Incremental single source shortest paths in sparse digraphs 摘要: Given a directed graph [math]\displaystyle{ G = (V, E, \mathbf{w}) }[/math] with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graph [math]\displaystyle{ G }[/math]. In a very recent paper, [Gutenberg et. al., 2020] proposed a deterministic algorithm for this problem with [math]\displaystyle{ \tilde{O}(n^2\log W) }[/math] total update time, where [math]\displaystyle{ n = \|V\| }[/math] and [math]\displaystyle{ W }[/math] denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions [math]\displaystyle{ m }[/math] is [math]\displaystyle{ \tilde{\Omega}(n^2) }[/math], their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzinger et. al., 2014], whose algorithm is randomized and works in [math]\displaystyle{ \tilde{O}(mn^{0.9}\log W) }[/math] total update time under the assumption of oblivious non-adaptive adversary. In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with [math]\displaystyle{ \tilde{O}(m^{5/3}\log W) }[/math] total update time. The second one is a randomized algorithm with [math]\displaystyle{ \tilde{O}((mn^{1/2} + m^{7/5})\log W) }[/math] total update time, which improves over both previous results when [math]\displaystyle{ m = O(n^{1.42}) }[/math]; moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break the [math]\displaystyle{ O(mn) }[/math] bound with adaptive adversaries for sparse graphs. Joint work with Shiri Chechik from Tel Aviv University.
9:40 -- 10:10	白宗磊北京大学	题目: The approximability of ferromagnetic 2-spin systems 摘要: Spin systems model the interactions between neighbors on graphs, An important special case is when there are only 2 spins, which encompass many important models in sampling and counting problems, including the famous Ising model, Hard-core model, etc. The approximability of 2-spin systems is widely studied in statistical physics, machine learning, probability theory, and theoretical computer science. The partition function can be viewed as polynomial on the external fields. For bounded degree graphs, I will present the zero-free region for ferromagnetic 2-spin systems, which implies an FPTAS based on the method introduced by Barvinok. On the other hand, we give #BIS-hard result for the external fields on the interval with respect to the degree bounds. The upper bound of the interval coincides with boundary of the zero-free region, which implies a complexity transition at the point.
10:10 -- 10:40	包奇复旦大学	题目: 基于拉普拉斯求解器的图数据挖掘算法摘要: 2004年，耶鲁大学教授 Daniel A. Spielman 提出了一种基于图稀疏化的求解拉普拉斯矩阵方程组的快速近似算法，并随后开发出了相关的代码库 Laplacians.jl。该算法时间复杂度低且精度高，其代码库在实际运行过程中效果良好。如何运用该求解器来有效解决图数据挖掘中遇到的问题？本报告将通过展示几个具体的案例来说明。
茶歇
10:55 -- 11:25	李斌电子科技大学	题目: 基于社交网络的拍卖机制设计理论研究摘要: 拍卖是资源分配最有效的形式。传统的拍卖机制面临着参与人数少，竞争不激烈的问题，这不仅会导致资源分配的低效性，还会限制卖家出售资源所获得的收益。在本次分享中，我们提出一套基于社交网络的拍卖机制框架。在该框架中，所有潜在的买家构成一张网络，网络中的节点只能和其邻居进行信息交换；卖家位于网络中的某个节点，并且在初始状态下，只有卖家的邻居知晓有关拍卖的信息。我们的目标是激励卖家的邻居主动分享拍卖信息给他们网络中的邻居，并由此形成级联反应，最终使得网络中所有买家知晓拍卖信息并参与进拍卖中来。这种内生的信息分享行为不仅会使得物品得到更有效的配置，也能够潜在地提高卖家的收益。我们刻画了所有满足个体理性，激励相容的传播拍卖机制；此外，我们具体分析了两类传播拍卖场景：无权网络场景和有权网络场景。针对这两类场景，我们设计了相应的传播拍卖机制，这些机制不仅能够激励信息传播，而且相比于传统拍卖，卖家的收益以及物品配置的效率上都得到了理论性的提升。
11:25 -- 11:55	王思为国防科学技术大学	题目: 基于后期融合的大规模多视图算法研究摘要: 物体的不同视图描述了物体的不同特性,如何利用这些视图的互补信息和兼容信息充分发挥各自优势,规避各自局限,是目前学术界研究的热点问题,这类信息融合的方法统称为多视图学习算法。与单视图学习算法不同,多视图学习算法能够学习到的特征更加全面,也更加鲁棒，但是现有的多视图聚类受限于样本立方的复杂度而限制了在大规模数据集上的应用。本报告基于我们所提出的基于后期融合的大规模多视图聚类算法，并提出尽可能多的现有大规模多视图算法的关键技术问题。
午餐
14：00 -- 14:30	吴步娇中科院计算所	题目: 有限辅助比特下CNOT电路的优化摘要: 由于量子计算机现阶段实现过程中的消相干问题，通过并行化量子电路来降低电路深度对量子算法的有效实现具有很大的价值。我们证明了任何n量子比特的CNOT电路在有[math]\displaystyle{ m }[/math]个辅助比特的情况下都可以优化为深度[math]\displaystyle{ O(\log n + n^2/(n+m)\log (n+m)) }[/math]。我们也证明了该算法得到的深度是渐近最优的。此外，因为当下较为流行的一种量子设备——超导量子电路的量子比特的连通性具有一定限制。因此，我们也考虑了带拓扑约束的CNOT电路的优化，并给出了相应的下界。
14：30 -- 15:00	张舒山东大学	题目: 最长公共样本子序列算法摘要: 寻找基因组中的保守基因在大豆分子育种、疫苗研发等研究中具有重要意义。为找到在不同的基因组中次序保持一致的保守基因序列，我们提出了带索引的最长公共样本子序列问题。给定两个线性基因组以及每个线性基因组的索引基因子序列，要求找到这两个线性基因组的一个最长公共样本子序列，并且该最长公共样本子序列的一个子序列和给定的索引基因子序列相同。为解决这一问题，我们提出了一个动态规划算法，此算法所需的时间和空间有随着索引基因子序列长度的增加而减少的趋势。我们在23对人/大猩猩染色体对上进行了实验，并分别找到了它们的最长公共样本子序列，这些子序列的基本单元为已经注释的基因或者伪基因，即一段连续的碱基序列。通过比较算法得到的伪基因和已经注释的基因，在人的7号和16号染色体上，我们分别找到超过1000和500个伪基因在人和大猩猩染色体对中顺序一致并且与任何已经注释的基因没有重叠，这些伪基因中很有可能存在一些新的基因或者motif。
15：00 -- 15:30	张文博上海交通大学	题目: 互模拟等价性验证问题研究摘要: 判定两个系统在语义上是否等价是验证领域的一个基本问题。互模拟等价是最受研究者们关注的等价关系之一。近年来，有不少无限状态系统上的互模拟等价问题都取得了重要突破。本次报告中，我们将会对领域内最新的研究成果和技术做一个尽可能全面的总结，并介绍我们的一些最新结论。
茶歇
15：45 -- 16:15	刘明谋南京大学	题目: 关于简洁数据结构复杂度的一些研究摘要: 数据结构是计算机科学的基石。本报告考虑了三个根本的数据结构问题的简洁数据结构。首先我们为范围最值查询问题证明复杂度下界。我们为该问题证明了首个复杂度下界，并且该下界证明了当前最好的算法在常数时间复杂度下的最优性。我们通过彻底重构前人的复杂度下界证明技术，使得我们不再只能证明平均情况的复杂度下界，而是能够证明更高的最坏情况的复杂度下界。然后我们考虑动态的近似集合成员查询问题（也被称为布隆过滤器问题）。我们考虑了一个具有很强现实意义、有趣但又很少被理论界考虑的设定：动态的数据结构可以使用动态的空间占用，但是其空间占用仅依赖于当前数据集的大小，而不是预先估计的最大大小。在这样的设定中，我们为动态的近似集合成员查询问题构造了目前为止在所有意义上的最优的数据结构：在空间上，它是唯一一个解决该问题的简洁数据结构；在时间上，它的所有更新和查询操作都可以在最坏情况的常数时间内完成。我们的数据结构为 Pagh, Segev和Wieder (FOCS 2013) 提出的开放性问题给出了一个肯定的回答。最后我们考虑另一个根本性的数据结构问题，字典问题。我们构思了一种全新的思路来处理经典的字典数据结构中会导致空间浪费的“溢出”问题。通过这样的全新策略，我们的额外空间开销从个[math]\displaystyle{ O(n(\log n)^{2/3}\log\log n) }[/math]比特降低到了个[math]\displaystyle{ O(n\log\ldots\log n) }[/math]比特，同时也保证了所有的更新操作和查询操作都可以在最坏情况的常数时间内完成。我们的数据结构为 Arbitman, Naor和Segev (FOCS 2010) 提出的开放性问题给出了一个肯定的回答。
15：15 -- 16:45	秦旭东华东师范大学	题目: 量子程序的互模拟验证摘要: 量子进程代数是基于经典的进程代数提出的，用于量子程序的形式化验证。量子进程代数有一种重要的应用，就是形式化地验证量子通信协议。其中有一种想法是，只要有合适的对行为等价性的定义以及一个判定方法，就可以判断一个协议的实现是否与该协议的规范是否是一致的，即可验证协议。本论文中考虑的量子基互模拟对量子程序来说便是一个方便使用的行为等价性定义。我们设计并实现了两个on-the-fly 算法，用于检测两个量子CCS 编写的量子程序之间的强基互模拟以及弱基互模拟。此外，我们还定义了基于分布的量子程序基互模拟，其在表现量子操作的等价性方面有更好的效果。我们同样实现了一个基于分布的量子程序基互模拟检测算法，并将其与基于状态的算法进行了比较实验。对上述算法，我们证明了算法的可终止性与正确性，并分析了算法的时间复杂度。并且基于算法的实现我们开发了一个工具QBisim，用于验证各种有名的量子协议，例如量子隐态传输协议、量子密钥分发协议、BB84 量子密钥分配方案等。我们通过工具对这些量子通信协议进行了实验，实验结果表明了工具是有效的。
16:45 -- 18:00	专题讨论：读博经历与求职经验分享会嘉宾：黄棱潇（华为TCS实验室）；李乾（深圳大学）; 刘正阳（北京理工大学）；邵帅（牛津大学）；张驰豪（上海交通大学)

TCSPhD

General Information

会议日程

报告人个人简介

Navigation menu

Search