ADL128《理论计算机科学—图、网络与解空间的连通性理论》开始报名

CCF学科前沿讲习班

The CCF Advanced Disciplines Lectures

ADL第128期

主题 理论计算机科学—图、网络与解空间的连通性理论

  2022年8月15日-8月17日 南京(线上线下同步举办)

本期CCF学科前沿讲习班ADL128《理论计算机科学—图、网络与解空间的连通性理论》，将对理论计算机科学前沿的一系列最新进展进行讲解。 我们以“图、网络与解空间的连通性”这一主题为线索，将会关注近年来在高效算法理论方面的一系列关键进展，以及与之相关的重要应用。相信学员经过本次讲习班，能够开阔视野，体会如何系统地解决计算机科学关注的问题，并且对各种计算现象背后的本质原理有更加深刻的理解。

本期ADL邀请了6位来自国内外著名高校与企业科研机构活跃在前沿领域的专家学者做主题报告。彭泱(Richard Peng)副教授将在第一天以及第二天上午，分别讲解近线性时间网络流算法中的优化算法以及数据结构。尹一通教授将在第一天以及第二天介绍约束满足解空间的连通性与约束满足解的快速采样。刘景铖副教授将在第一天下午讲图稀疏化理论导引。郭珩教授将在第二天下午讨论部分拒绝采样与网络可靠性。第三天，段然副教授将介绍高效的容错连通性和距离查询数据结构，朱夏博士将讲解网络基础理论洞察。通过三天教学，旨在带领学员了解理论计算机科学的前沿进展，并且体会背后的本质原理。

学术主任：尹一通 教授 南京大学

主办单位：中国计算机学会

协办单位：南京大学计算机软件新技术国家重点实验室

本期ADL主题《理论计算机科学——图、网络、与解空间的连通性理论》，由南京大学尹一通教授担任学术主任，邀请到段然（副教授，清华大学），郭珩（教授，爱丁堡大学），刘景铖（副教授，南京大学），彭泱（副教授，滑铁卢大学/卡内基梅隆大学），尹一通（教授，南京大学），朱夏（华为网络基础理论团队负责人，华为）6位专家做专题讲座。

活动日程：

特邀讲者1：段然，副教授，清华大学

讲者简介：段然，清华大学交叉信息研究院副教授。本科毕业于清华大学计算机系，2011年获得密歇根大学计算机系博士学位，导师是Prof. Seth Pettie，方向为理论计算机科学。之后在德国马克斯普朗克信息学研究所任博士后研究员，其间获得洪堡奖学金。2014年8月加入清华大学交叉信息研究院，主要研究方向为图论算法、数据结构、计算博弈论等。线性时间近似最大匹配的成果曾发表在顶级期刊Journal of ACM，在国际顶级会议STOC、FOCS、SODA、ICALP上发表论文20余篇。
报告题目：高效的容错连通性和距离查询数据结构
报告摘要：在计算机网络、道路网络和社交网络中，连通性和最短路问题都是各种应用的基础。而现实中的网络往往并不完全稳定，例如交通拥堵、网络节点故障等都会造成网络的结构发生临时的改变，所以高效的动态数据结构是算法领域的核心问题之一。因其效率远远高于全动态的数据结构，近些年来点（边）失效模型也是新兴的研究方向，这个模型也被称为容错模型（failure-prone model）。它研究在一个给定的网络上建造一个半动态的数据结构，使得如果每次查询时故障的点（边）的个数不超过一个界限d，我们能够很快地得到任意两点间不经过故障点（边）的连通性或距离。本报告将介绍一些近年来这方面的最新成果和它们的设计思路，以及可能的研究方向。

特邀讲者2：郭珩，教授，爱丁堡大学

讲者简介：Heng Guo (郭珩) is a reader in algorithms and complexity in the School of Informatics, the University of Edinburgh. He came to Edinburgh after spending two years in Berkeley and in London. Before that, he completed his Ph.D. in the University of Wisconsin - Madison in 2015, which has won the EATCS Distinguished Dissertation award. He has also won the best paper award of ICALP 2018 (joint with Mark Jerrum).
报告题目：部分拒绝采样与网络可靠性
报告摘要：Partial rejection sampling (PRS) is an algorithm which bridges approximate counting/sampling and Lovasz local lemma. We will explain how PRS works, show its correctness, and discuss a formula for its expected running time in some special but very useful cases. With this technique, we will give a fully polynomial-time randomised approximation algorithm for all-terminal network reliability. Time permitting, we will cover a few other related applications as well.

特邀讲者3：刘景铖，副教授，南京大学

讲者简介：Jingcheng Liu (刘景铖) is an Associate Professor at Nanjing University. Before that, he completed undergrad at SJTU and PhD at UC Berkeley, then he was a postdoc at Caltech. His research focuses on the interplay between phase transitions in statistical physics, locations of zeros of graph polynomials, and algorithmic questions such as the tractable boundaries of approximate counting, sampling and inference.
报告题目：图稀疏化理论导引
报告摘要：Given an arbitrary graph G, can you find a sparse graph that approximates G in some sense? We will survey a beautiful line of work, starting with the celebrated notion of cut-approximator in the works of Karger and Benczur-Karger. Intuitively, one tries to approximate the "connectedness" of a given graph. As a special case, if one tries to approximate a complete graph with a d-regular graph for a constant d, such sparsifiers are known as the expander graphs, and it has found applications in networking, coding theory, analysis of algorithms and many more . Besides expanders, we will also discuss a powerful generalization of cut-approximator known as spectral approximations. It turns out that one can find spectral approximations for every weighted graph very efficiently, and this has been a useful and versatile (algorithmic) primitive for many problems in graph theory and beyond.

邀讲者4：彭泱，副教授，滑铁卢大学/卡内基梅隆大学

讲者简介：Richard Peng (彭泱) is an associate professor in the Cheriton School of Computer Science at the University of Waterloo. He is known for fast algorithms for solving graph structured linear systems, and his current research revolves around the design, analysis, and implementation of efficient algorithms. Richard was a recipient of the 2011 Microsoft PhD Fellowship, an NSF CAREER Award, and the 2021 ACM-SIAM Symposium on Discrete Algorithms Best Paper Award.
报告题目：近线性时间网络流算法
报告摘要：This two-part talk will survey recent developments in optimization algorithms and data structures for computing network flows. Flows, or combinations of paths, have origins in routing and assignment problems, and are closely related to many core primitives in data science. Previously, even for finding the maximum of edge-disjoint s-t paths, the best running time bound was at least m^{4/3}. A combination of these new tools on the other hand led to an algorithm for optimizing a flow to minimize general edge-separable convex functions whose asymptotic running time is almost-linear in the graph size. The first half of the talk will overview approaches for computing network flows, then discuss the connections with continuous optimization and graph approximation theory critical for overcoming bottlenecks facing purely combinatorial methods. The second half of the talk will discuss recent developments of speeding up second order optimization methods using dynamic graph data structures, with focus on tree compression and divide-and-conquer schemes critical for fast maintenance of edge-sparsifiers and vertex eliminations.

特邀讲者5：尹一通，教授，南京大学

讲者简介：尹一通，2003年本科毕业于南京大学，2009年博士毕业于耶鲁大学，现为南京大学计算机科学与技术系教授。开设课程《高级算法》、《组合数学》等。研究方向是理论计算机科学，具体方向为随机算法、计算相变、大数据计算理论等。在JACM、SICOMP、STOC、FOCS、SODA等理论计算机科学期刊与会议发表论文四十余篇。先后在微软研究院、威斯康星大学麦迪逊分校、加州大学伯克利分校Simons计算理论研究所、瑞士洛桑联邦理工学院 (EPFL) 做访问学者。主持国家重点研发计划项目“数据科学的若干基础理论”、国家自然科学基金优秀青年科学基金项目“理论计算机科学”等。获得CCF/IEEE CS青年科学家、教育部新世纪优秀人才、中创软件人才奖等，指导博士生获CCF优秀博士学位论文奖。获南京大学中青年骨干教师、计算机系奖教金、杜厦奖教金、南京大学五四青年奖章等。执教《高级算法》和《组合数学》均被本科生选为“我心目中的好课程”。
报告题目：约束满足解空间的连通性与约束满足解的快速采样
报告摘要：约束满足问题（constraint satisfaction problem, CSP）是计算机科学关注的一类基本的计算问题。例如经典的可满足性判定（SAT）问题——这一人类已知的首个NP完全问题，即是约束满足问题的一个特例。约束满足解空间的几何性质，关系到与约束满足问题相关的诸多计算问题的计算复杂性。在本次讲座中，我们将介绍：作为约束满足问题解的存在性的充分条件“Lovasz局部引理”、约束满足解空间的连通性、以及对约束满足解的快速采样算法之间的联系。

特邀讲者6：朱夏，华为技术有限公司中央研究院高级专家

讲者简介：朱夏，华为技术有限公司中央研究院网络lab高级专家，负责华为网络基础理论团队。历任华为数据通信产品线广域优化首席专家、传输层研究专家、SD-WAN研究项目经理等。

报告题目：网络基础理论洞察及思考
报告摘要：随着应用快速发展，未来网络将面临超大带宽、极低时延、极致可靠、海量联结等需求，网络技术急需理论探索和纵深突破。在本次讲座中，我们将会从网络研究领域的各个理论方向，包括网络编码、网络优化、网络控制、网络测量、网络建模等，阐述当前的研究现状和成果，同时也介绍面临的数学理论难题。

学术主任：
尹一通，教授，南京大学

尹一通，2003年本科毕业于南京大学，2009年博士毕业于耶鲁大学，现为南京大学计算机科学与技术系教授。开设课程《高级算法》、《组合数学》等。研究方向是理论计算机科学，具体方向为随机算法、计算相变、大数据计算理论等。在JACM、SICOMP、STOC、FOCS、SODA等理论计算机科学期刊与会议发表论文四十余篇。先后在微软研究院、威斯康星大学麦迪逊分校、加州大学伯克利分校Simons计算理论研究所、瑞士洛桑联邦理工学院 (EPFL) 做访问学者。主持国家重点研发计划项目“数据科学的若干基础理论”、国家自然科学基金优秀青年科学基金项目“理论计算机科学”等。获得CCF/IEEE CS青年科学家、教育部新世纪优秀人才、中创软件人才奖等，指导博士生获CCF优秀博士学位论文奖。获南京大学中青年骨干教师、计算机系奖教金、杜厦奖教金、南京大学五四青年奖章等。执教《高级算法》和《组合数学》均被本科生选为“我心目中的好课程”。

时间：2022年8月15日-8月17日

线下地址（疫情允许的情况下）：南京•南京大学仙林校区国际会议中心

（南京市仙林大道163号南大国际会议中心）
线上地址：报名交费成功后通过邮件发送。

报名须知：

1、报名费：CCF会员2800元，非会员3600元。食宿交通费用自理。根据交费先后顺序，会员优先的原则录取，额满为止。疫情期间，根据政府疫情防控政策随时调整举办形式（线上、线下）。

2、报名截止日期：8月11日。报名请预留不会拦截外部邮件的邮箱，如qq邮箱。
3、咨询邮箱 : adl@ccf.org.cn

缴费方式：

在报名系统中在线缴费或者通过银行转账：

银行转账（支持网银、支付宝）：

开户行：招商银行北京海淀支行

户名：中国计算机学会

账号：110943026510701

请务必注明：ADL128+姓名

报名缴费后，报名系统中显示缴费完成，即为报名成功。

报名方式：请选择以下两种方式之一报名：

1、扫描（识别）以下二维码报名：

2、点击报名链接报名：https://conf.ccf.org.cn/ADL128

相关链接
线上线下同步举办-ADL127《AI+Science》开始报名