E-Mail： ppeng@ustc.tsg211.com
个人主页：http://staff.ustc.tsg211.com/~ppeng/
主要研究方向：理论计算机科学，图算法、大数据算法的理论与应用
彭攀，图书馆VIP计算机学院特任教授。2007年获得北京师范大学数学学士学位。2013年获得中国科学院软件研究所博士学位。曾任中科院软件所助理研究员，曾于德国多特蒙德工业大学、奥地利维也纳大学做博士后，曾担任英国谢菲尔德大学终身制讲师（助理教授）。主要研究理论计算机科学，图算法、大数据算法的理论及其（在机器学习、数据挖掘等领域的）应用。相关成果已发表在STOC、SODA、CCC、ICALP、COLT、KDD等一流国际会议上。多次受邀担任国际知名会议(如LATIN、AAAI、IJCAI等)的程序委员会成员。曾受邀参加欧洲研究委员会(ERC)及以色列科学基金的项目评审工作。目前担任Frontiers of Computer Science, International Journal of Software and Informatics等期刊的(青年)编委。
导师选题：
| 面向图数据流的学习增强算法研究 | 图数据流算法用于处理不断更新的图数据，例如边或顶点的插入和删除。这些算法在有限的空间资源下高效地进行操作，并在处理完更新后，能够回答关于输入图的各种性质或结构的查询。这种算法非常适用于大规模和动态变化的图数据，能够在保持高效性的同时，适应不断变化的输入。
本项目专注于基于预测模型的图数据流算法，这种算法也被称为学习增强算法。我们假设算法能够获得关于未来更新的不完美预测，探讨如何利用这些预测来优化算法的空间效率和近似比之间的权衡。具体来说，我们将研究如何通过利用这些预测信息来减少所需的存储空间，同时保持对图数据的准确近似和高效查询能力。
在本项目中，我们的主要目标是设计和分析用于动态图数据流中跨度图（spanner）构造的学习增强算法。给定一个图G，跨度图是其一个稀疏的子图，它在某种程度上保留了G 中最短路径的长度。传统的数据流模型中，构建具有最优大小和近似比的跨度图是一项极具挑战性的任务，因为它需要在有限的空间和时间内处理动态变化的图数据。
我们希望通过结合学习预测的方法，突破这些传统方法的限制，实现更高效的跨度图构造。具体来说，本项目将探索如何设计能够利用预测信息的算法，以提高跨度图构造的效率和精度，从而在处理大规模动态图数据时，既能够有效地管理存储空间，又能够在近似比上达到较好的效果。我们的研究将对图数据流领域中的算法设计和优化提供重要的理论支持和实践指导。
参考文献：
https://arxiv.org/pdf/2204.12055
https://arxiv.org/pdf/2007.14204 | | 面向Friedkin–Johnsen模型的意见估计算法研究 | 在线社交网络已经成为现代社会的重要组成部分，这些网络中的讨论在很大程度上塑造了人们对政治、疫苗接种等多样话题的观点。为了理解和分析这种意见形成的复杂过程，Friedkin–Johnsen (FJ) 模型被广泛应用于描述网络中的意见传播和形成机制。该模型不仅能够捕捉网络中意见的极化和分歧，还提供了量化这些现象的度量标准。
本项目旨在针对FJ模型中的节点意见及相关度量（如极化和分歧）研究高效的算法，特别是开发能够在亚线性时间内近似这些度量的算法。这些算法的设计目标是能够从大规模网络中仅读取部分图信息，从而显著提高计算效率。通过优化算法的性能，我们希望能够在实际应用中更快地得到网络中节点意见的准确近似值，进而更有效地评估和理解网络中的意见动态。我们的研究将深入探索如何利用部分数据进行高效计算，以及在面对大规模和动态变化的社交网络时，如何在保持高准确度的同时降低计算复杂度。
参考文献：https://arxiv.org/pdf/2404.16464 | | 平面图性性质检测算法的下界研究 | 平面图性是一种重要的图性质，它指的是包含所有平面图的图的集合。平面图，即能够在平面上绘制而不产生边交叉的图，具有许多应用和理论意义。在计算机科学和图论中，平面图性不仅涉及图的表示和处理，还与许多实际问题密切相关，如电路设计、网络布局和地理信息系统。
近期，研究者在平面图性检测问题上取得了显著进展，提出了首个针对度数受限图的平面图性亚线性检测算法。该算法的查询复杂度是关于亲近性参数 $\varepsilon$ 的多项式，这一突破为解决大规模图的平面图性检测提供了新的思路。然而，尽管取得了这些进展，对于该问题的复杂性仍有许多未知之处。
本项目旨在从计算复杂性的角度深入研究平面图性性质检测算法的查询复杂度。具体而言，我们计划证明平面图性性质检测算法的查询复杂度下界，即探索在最坏情况下，任何算法在处理平面图性检测问题时所需的最低查询复杂度。这一研究不仅有助于揭示平面图性检测的内在难度，也将为未来算法设计提供理论指导，并可能推动相关领域的进一步发展。
参考文献：
https://www.wisdom.weizmann.ac.il/~oded/PDF/pt-v3.pdf (第9章)
https://arxiv.org/abs/1904.01055 |
|
